Question

Calculate the time complexity of the following program fragments.

(a) 𝑓𝑜𝑟 (𝑖 = 1; 𝑖 ≤ 𝑛; 𝑖 ∗ = 2)

{

𝑥 = 𝑥 + 1

}

(b) 𝑓𝑜𝑟 (𝑖 = 1; 𝑖 ≤ 𝑛; 𝑖 + +)

𝑓𝑜𝑟 (𝑗 = 1; 𝑗 ≤ 𝑛; 𝑗 = 𝑗 ∗ 2)

{

… .

… .

}

Answer 1

a)

It is executed, for $i=1,2,4,8,...,2^n$

The time complexity:

$T(n)=\lfloor log_2n\rfloor$

b)

It is executed, n times for $j=1,2,4,8,...,2^n$

The time complexity:

$T(n)=n\lfloor log_2n\rfloor$