Help find the complexity of this algorithm

Question

I am trying 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 this is O (log (n) * log (log (n)) * log (log (n))):

• The loop "i" is executed until i = log (n)
• the 'j' loop runs until log (i) means log (log (n))
• the loop 'k' works as long as k = j → k = log (i) → k = log (log (n))

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

Answer 1

The complexity of time 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++;

This is obviously Theta (T ^ 3).

. . a = log_2 (i). a , 2. :

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

, , - (log_2 (n)) T, a for .

, .

Answer 2

?

:

, , . log10 float, cast (long int), , .9999999999. , . :

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

:

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

'j'- ' k'-loop .
( log n , n, log n)