Time complexity for two pieces of code

Question

We've got 2 pieces of code:

int a = 3; 
while (a <= n) {
    a = a * a;
}

And:

public void foo(int n, int m) { 
    int i = m; 
    while (i > 100) 
        i = i / 3; 
    for (int k = i ; k >= 0; k--) { 
        for (int j = 1; j < n; j*=2) 
            System.out.print(k + "\t" + j); 
        System.out.println(); 
    } 
}

What is the time complexity of them? I think that the first one is: O(logn), because it's progressing to N with power of 2.
So maybe it's O(log²n) ?

And the second one I believe is: O(nlog2n), because it's progressing with jumps of 2, and also running on the outer loop.

Am I right?

Answer 1

I believe, that first code will run in O(Log(LogN)) time. It's simple to understand in this way

1. Before first iteration you have 3 in power 1
2. After first iteration you have 3 in power 2
3. After second iteration you have 3 in power 4
4. After third iteration you have 3 in power 8
5. After fourth iteration you have 3 in power 16 and so on.

In the second code first piece of code will work in O(LogM) time, because you divide i by 3 every time. The second piece of code C times (C equals 100 in your case) will perform O(LogN) operations, because you multiply j by 2 every time, so it runs in O(CLogN), and you have complexity O(LogM + CLogN)

Answer 2

For the first one, it is indeed O(log(log(n))). Thanks to @MarounMaroun for the hint, I could find this:

l(k) = l(k-1)^2
l(0) = 3

Solving this system yields:

l(k) = 3^(2^k)

So, we are looking for such a k that satisfies l(k) = n. So simply solve that:

This means we found:

The second code is seems misleading. It looks like O(nlog(n)), but the outer loop limited to 100. So, if m < 100, then it obviously is O(mlog(n)). Otherwise, it kind of depends on where exactly m is. Consider these two:

• m: 305 -> 101 -> 33
• m: 300 -> 100

In the first case, the outer loop would run 33 times. Whereas the second case would cause 100 iterations. I'm not sure, but I think you can write this as being O(log(n)).