I just learned time complexity and I'm trying to calculate the theta for this code:

for(i=2; i<n; i=i 1) {
    for(j=1;j<n;j=j*i) {
        count  ;
    }
}

I though that its n*log(n), because the first loop complexity is n, and the second loop is log(n). but I've been told the answer is n.

can someone tell what is the correct answer and explain why?

CodePudding user response：

the second loop isn't O(log n) because the multiplier i keeps increasing. It's O(log_in). This causes the number of repetitions of the inner loop to be inversely proportionally to i, so the inner loops average out to the same number of iterations as the outer loop, making the whole thing O(n).

CodePudding user response：

In the inner loop, j starts at 1 and on each cycle it is multiplied by i, so it takes the values 1 = i⁰, i¹, i², i³, etc. The iteration stops when j == i^k for that integer k such that i^k-1 <= n < i^k. That takes k 1 iterations, and each iteration performs a constant number of operations.

Logarithms with base > 1 are strictly increasing functions over the positive real numbers, so the relations above are preserved if we take the base-i logarithm of each term: k-1 <= log_i(n) < k. With a little algebra, we can then get k 1 <= log_i(n) 2. Since k 1 is the number of iterations, that gives us that the number of iterations of the inner loop for a given value of i is O(log_i(n)).

The overall cost of the loop nest, then, is bounded by Σ_i=2,n O(log_i(n)). That can be written in terms of the natural logarithm as Σ_i=2,n O(log_e(n) / log_e(i)). Dropping the 'e' subscript and factoring, we can reach O((log n) Σ_i=2,n (1/(log i))). And that's one answer.

But for comparison with the complexity of other algorithms, we would like a simpler formulation, even if it's a little looser. By observing that 1/log(i) decreases, albeit slowly, as i increases, we can observe that one slightly looser bound would be O((log n) Σ_i=2,n (1/(log 2))) = O((log n) * (n-1) / (log 2)) = O(n log n). Thus, we can conclude that O(n log n) is an asymptotic bound.

Is there a tighter bound with similarly simple form? Another answer claims O(n), but it seems to be based on a false premise, or else its reasoning is unclear to me. There may be a tighter bound expression than O(n log n), but I don't think O(n) is a bound.