help in find complexity of this algorithm

Question

Hi, 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))).

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

Answer 2

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.