What is the growth function of every case (a-d)?

Question

a)

for(i = 1; i*i <= N; i = 2*i);

b)

for(i = 1; i <= N; i = 2*i);
    for(j = 1; j <= i; j = j+1);

c)

for(i = 1; i*i <= N; i=i+1);
    for(j=1; j <= i ; j=j+1);

d)

for(i = 1; i*i <= N; i=i+1)
    for(j = 1; j <= i ; j = 2*j);

Comments

please solve this questn

Answer 1

Using lg for log₂

(a)

for(i = 1; i*i <= N; i = 2*i);

i is multiplied by 2 in each iteration and stops when equals √N. So, loop will run for lg (√N) times and time complexity = $\Theta( \lg (\sqrt N ))$

(b)

for(i = 1; i <= N; i = 2*i)
    for(j = 1; j <= i; j = j+1);

Outer loop runs for lg(N) times. For each i, Inner loop runs for i times. So, total number of iterations 

= 1 + 2 + 4 + 8 + ... N (Sum to N terms of GP with a = 1, r = 2, and number of terms = log n)
= $\Theta (N)$ 

(c)

for(i = 1; i*i <= N; i=i+1)
    for(j=1; j <= i ; j=j+1);

The outer loop runs for √N times. For each i, the inner loop runs i times. So, number of iterations 

= 1 + 2 + ... + √N

= √N * (√N+1) /2 = $\Theta (N)$

(d)

for(i = 1; i*i <= N; i=i+1)
    for(j = 1; j <= i ; j = 2*j);

The outer loop runs for √N times. For each i the inner loop runs lg i times. So, total number of iterations

= lg 1 + lg 2 + lg 3 + ... lg √N
=lg (1 * 2 * 3 * ... *√N)
=lg ((√N)!)
= $\Theta (√N \lg √N)$ using Stirling's approximation)
http://mathworld.wolfram.com/StirlingsApproximation.html

Comments

Please elaborate how sum to n terms of GP (1+2+4... N) becomes O(N)

---

a = 1, r = 2 and number of terms will be log n

So, S = a(rⁿ - 1)/(r-1)

= 1 (2^{log n} -1)/(2-1)

= n - 1.