help in find complexity of this algorithm

Question

i try to find the complexity of this algorithm:

m=0;
i=1;
while (i<=n)
{
   i=i*2;
   for (j=1;j<=(long int)(log10(i)/log10(2));j++)
     for (k=1;k<=j;k++)
          m++;
}

I think it is O(log(n)*log(log(n))*log(log(n))):

The 'i' loop runs until i=log(n)
the 'j' loop runs until log(i) means log(log(n))
the 'k' loop runs until k=j --> k=log(i) --> k=log(log(n))

therefore O(log(n)*log(log(n))*log(log(n))).

Sheldon L. Cooper · Accepted Answer · 2010-08-30 13:34:22Z

3

The time complexity is Theta(log(n)^3).

Let T = floor(log_2(n)). Your code can be rewritten as:

  int m = 0;
  for (int i = 0; i <= T; i++)
   for (int j = 1; j <= i+1; j++)
    for (int k = 1; k <= j; k++)
     m++;

Which is obviously Theta(T^3).

Edit: Here's an intermediate step for rewriting your code. Let a = log_2(i). a is always an integer because i is a power of 2. Then your code is clearly equivalent to:

m=0;
a=0;
while (a<=log_2(n))
{
   a+=1;
   for (j=1;j<=a;j++)
     for (k=1;k<=j;k++)
          m++;
}

The other changes I did were naming floor(log_2(n)) as T, a as i, and using a for loop instead of a while.

Hope it's clear now.

edited Aug 30, 2010 at 13:34

answered Aug 28, 2010 at 22:31

Sheldon L. Cooper

3,27021 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Sheldon L. Cooper Over a year ago

More specifically, I think the value of m as a function of T would be: m(T) = choose(T+2, 3) + (T+1)*(T+2)/2

Sheldon L. Cooper Over a year ago

Simplifying, it results in: m(T) = (T+1)(T+2)(T+3)/6

moti Over a year ago

thank you very much, your explination is very clear. m(n) is a logaritm graph, but i didnt understood why m(T) = choose(T+2, 3) + (T+1)*(T+2)/2 –

Sheldon L. Cooper Over a year ago

We want to count the number of triples (i, j, k) obtained by the loop indexes. Let's first count the triples with j less than or equal i (and not equal to i+1), i.e. triples (i, j, k) satisfying 1 <= k <= j <= i <= T. This is exactly choose(T + 3 - 1, 3), the number of combinations with repetition of 3 elements out of T. You can read more about it here: en.wikipedia.org/wiki/….

Sheldon L. Cooper Over a year ago

Now consider the triples with j equal to i+1, i.e. triples (i, i+1, k). For each i, from 0 to T, there are i+1 values for k. Hence, there are 1 + 2 + ... + (T+1) triples of this kind. This is the T+1 Triangular Number, i.e. (T+1)(T+2)/2. More info here: en.wikipedia.org/wiki/Triangular_number

|

rudi-moore · Accepted Answer · 2010-08-27 15:48:05Z

1

Is this homework?

Some hints:

I'm not sure if the code is doing what it should be. log10 returns a float value and the cast to (long int) will probably cut of .9999999999. I don't think that this is intended. The line should maybe look like that:

for (j=1;j<=(long int)(log10(i)/log10(2)+0.5);j++)

In that case you can rewrite this as:

m=0;
for (i=1, a=1; i<=n; i=i*2, a++)
    for (j=1; j<=a; j++)
        for (k=1; k<=j; k++)
            m++;

Therefore your complexity assumption for the 'j'- and 'k'-loop is wrong.
(the outer loop runs log n times, but i is increasing until n, not log n)

answered Aug 27, 2010 at 15:48

rudi-moore

2,7101 gold badge19 silver badges16 bronze badges

2 Comments

moti Over a year ago

but j is until log(i) not i itself

rudi-moore Over a year ago

Yes, but the value of i doubles in every loop. So in the last loop i == n (not i == log n). a is log (i+1).

Collectives™ on Stack Overflow

help in find complexity of this algorithm

2 Answers 2

8 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

8 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related