1

I want to calculate Big O of x++ in below algorithm.

for (int i = 2;i < n;i*=2)
    for(int j = i;j < m;j*=j)
       x++;

I think a lot about it, but I can't solve it. How can I solve it?

5
  • Big-O notation in terms of which variable? m or n? Nov 30, 2011 at 15:20
  • In both of them.It depends on both of them. Nov 30, 2011 at 15:20
  • The asymptotic behaviour is really only affected by m. As soon as n exceeds m then the runtime won't increase. Nov 30, 2011 at 15:23
  • "I think a lot about it" - what have you thought so far?
    – AakashM
    Nov 30, 2011 at 15:27
  • This case is very interesting. Thank you for having shared it. Apr 3, 2014 at 22:35

4 Answers 4

6
O(lg(n) * lg(lg(m)))

at most lg(n) for outer loop and lg(lg(m)) for the other.

EDIT: more help to prove:

lets change the variables :

nn = lg(n);
mm = lg(m);

the code will become:

for (int i = 1;i < nn;i++)
    for(int j = i;j < mm;j *= 2)
        x++;

now the runtime will be O(nn * lg(mm)).

EDIT(2): the bound can become tighter(because we have j = i in the second loop, not j = 1)

if nn >= mm then (x++) = theta(mm * lg(mm)) = theta(lg(m) * lg(lg(m)))

and

if nn < mm then (x++) = theta(nn * lg(mm)) = theta(lg(n) * lg(lg(m)))

1
  • 2
    Are you sure we can't get a tighter bound by knowing that it uses j=i instead of j=1?
    – hugomg
    Nov 30, 2011 at 15:45
5

Obviously, the outer loop is O(log2(n)) as i is doubled with each iteration from 2 until n exclusive. So:

2x < n
⇔ log2(2x) < log2(n)
x < log2(n)

So it requires at most log2(n) iterations of the outer loop until i < n is no longer fulfilled, thus O(log(n)).

The inner is a little tricky as the current value of i of the outer loop is used to initialize j of the inner loop. Additionally, j is multiplied with itself (i. e. j2) with every iteration. So:

j2x < m
⇔ logj(j2x) < logj(m)
⇔ 2x < logj(m)
⇔ log2(2x) < log2(logj(m))
x < log2(logj(m))

So it requires at most log2(logj(m)) iterations of the inner loop until the condition j < m is no longer fulfilled, thus O(log(log(m))). And if we ignore the bases, we can estimate the total complexity at O(log(n)·log(log(m))).

1

O(log(n) * log log(m)) the inner gets executed log log m times.

1
  • This implies that it's O(log(n)) if m is fixed. But this is not the case. Nov 30, 2011 at 15:31
0

I have tried to deduce the order of growth complexity of your algorithm, in methodical way. Unfortunately, I couldn't do so with j that variates at each innerloop iteration.

Nonetheless, I came up with a formula with a constant factor k instead of j.

Your algorithm, according to my suggestion, should look like the following:

for (int i = 2;i < n;i*=2)
    for(int j = i;j < m;j*=k)
       x++;

The solution is as follows:

enter image description here

enter image description here

Meanwhile, I will attempt to find a solution fitting exactly your initial problem.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.