CODEWITHSUNDEEP
timecomplexity-theory
user2931957
user2931957

Reputation: 37

Nested for-loop complexity

What is the growth function of every case (a-d)?
I struggle to find the running time of each nested for loop. I guess I have found some of them but I am not sure.

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);

Upvotes: 2

Views: 272

Answers (2)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

You can formally solve the code fragments using Sigma Notation:

a)

enter image description here

b)

enter image description here

c)

enter image description here

d)

enter image description here

Upvotes: 1

LeartS
LeartS

Reputation: 2896

This is what I got:

Growth:

  1. O(log(sqrt(N)))
  2. O(N)
  3. O(N)
  4. O(log(sqrt(N)!)) = O(sqrt(N)*log(sqrt(N))) using Stirling's approximation

Exact numbers: ([X] is the integer part of X)

  1. [log([sqrt(N)])]+1
  2. 2^([log(N)]+1)
  3. [sqrt(N)]*[sqrt(N)+1]/2
  4. not really sure.

And here's a little check: I implemented the for loops with a counter, this is the output for N=10000000:

a(N)= 12           a(10*N)= 14
b(N)= 16777216     b(10*N)= 134217728
c(N)= 5000703      c(10*N)= 50005000
d(N)= 33861        d(10*N)= 123631

EDIT: as requested, explanations
First of all, some consideration:

  • we are treating integers, so of any real function you see (sqrt and log basically) you should actually take the integer part.
  • as almost always in computer science, log = log base 2

Now:

  1. i goes from 1 to sqrt(N), but it does so "using" only powers of 2. There are log(M) (+1 actually) powers of 2 between 1 and M, so with M = sqrt(N) you get the formula.

  2. i goes from 1 to N by powers of 2, as before. For every i there are i js. If we sum the js for every i:
    1 + 2 + 4 + 8 + 16 + ... + 2^log(N) = 2N - 1 = O(N)

  3. i goes from 1 to sqrt(N). For each i, there are i js. As before we sum the number of js for each i:
    1 + 2 + 3 + 4 + 5 + ... + sqrt(N) = sqrt(N) * sqrt(N+1) / 2 = O(N)

  4. i goes from 1 to sqrt(N). For every i, j goes from 1 to i using only powers of 2, therefore for every i you have log(i) js. If you sum all the js for every i you get:

    log(1) + log(2) + log(3) + log(4) + log(5) + ... + log(sqrt(N))
    For the property of logarithms log(a) + log(b) = log(a*b). Apply this to our summation:
    log(1*2*3*4*5*..*sqrt(N)) = log( sqrt(N)! )
    Which is the result. Given that the factorial is a problem for large numbers, you can use Stirling's approximation: ln(N!) -> N*log(N) - N for large numbers.

Example of the difference using integer part

Consider 2. The integer part of log(N) stays the same until N doubles. Which means, for example, that this for cycle execs the same number of operations (131072) for N=65536 and for N=131071. When N becomes 131072 (just one more), the number of operations doubles (262144).

Upvotes: 4

Related Questions