Finding the complexity of Loops

Question

I'm given this algorithm and I'm told to find the complexity of it big theta.

for (i = 1; i <= n; i++) {
    j = n;
    while( j >= 1) {
        j = j/3;
    }

}

I know outer for loop runs n times. The while loop is more tricky though, Is it possibly log n (of base 3). In total making it n*log₃n

Is this correct?

Yes, this is correct. The number of times the inner loop executes is fixed at log n, base 3. — Sergey Kalinichenko, Feb 05 '16 at 01:14
The (base 3) is wrong. You can convert `log x(base n) = c log x(base m)`. Given that in Theta notation, we drop the coefficient of each term, adding (base 3) is wrong. Therefore the correct form of your answer should be `nlogn`. — Aron, Feb 05 '16 at 01:49
Possible duplicate of [How to find time complexity of an algorithm](http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) — Paul Hankin, Feb 05 '16 at 03:51

score 0 · Answer 1 · answered Feb 06 '16 at 15:18

There is an outer for loop of size n. It contributes a complexity of a factor of n to the over all complexity.

Let's say inner while loop runs for m times. After i'th iteration, the value of j will be n/(3^i). We will run this till n/(3^i) > 1. Therefore,

=> n/(3^i) = m
=> n = 3^m
=> log(n) = log2(3) * m
=> m = O(log(n))

So, for loop contributes to O(n) and while loop contributes to O(log(n)). Complexity of nested loop becomes O(n log(n)).

1 Answers1