Find the total number of basic operations executed in the wo

Find the total number of basic operations executed in the worst case by the following code. Assume n = 2^k for some positive integer k. j= 1 while (j lessthanorequalto 3^logn) {perform j basic operation j = j*3}

Solution

Answer

the loop will run for until j > 3^{log n} where n = 2^k

therefore in the worst case scenario,

j has to be equal to 3^{k log 2} = 3^0.3k (assuming that the base here is 10)

if k = 10, then j needs to be equal to 27, which will take 3 steps (= 0.3 * 10)

if k = 20, then j needs to be equal to 729 which will take 6 steps (= 0.3 * 20)

so, we can deduce that the total number of basic operations executed in the worst case is (0.3 * k) where k is any positive integer.