CODEWITHSUNDEEP
ctime-complexity
Alfa Hores
Alfa Hores

Reputation: 394

what is the correct time complexity for this following code?

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?

Upvotes: 0

Views: 121

Answers (2)

John Bollinger
John Bollinger

Reputation: 180113

In the inner loop, j starts at 1 and on each cycle it is multiplied by i, so it takes the values 1 = i0, i1, i2, i3, etc. The iteration stops when j == ik for that integer k such that ik-1 <= n < ik. That takes k+1 iterations.

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 <= logi(n) < k. With a little algebra, we can then get k+1 <= logi(n) + 2. Since k+1 is the number of iterations, and every inner-loop iteration has the same, constant cost, that gives us that the cost of the inner loop for a given value of i is O(logi(n)).

The overall cost of the loop nest, then, is bounded by Σi=2,n O(logi(n)). That can be written in terms of the natural logarithm as Σi=2,n O(loge(n) / loge(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.

Update:

Thanks to @SupportUkraine, we can say that the performance is indeed bounded by O(n). Here's an argument inspired by their comment:

We can observe that for all i greater than sqrt(n), the inner loop body will execute exactly twice, contributing O(n) inner-loop iterations in total.

For each of the remaining sqrt(n) outer-loop iterations (having i < sqrt(n)), the number of inner-loop iterations is bounded by O(logi(n)) = O(loge(n)). These contribute O(sqrt(n) * log(n)) iterations in total.

Thus, the whole loop nest costs O(sqrt(n) * log(n)) + O(n). But sqrt(n) * log(n) grows more slowly than n, so this is O(n).

Upvotes: 4

Barmar
Barmar

Reputation: 780798

the second loop isn't O(log n) because the multiplier i keeps increasing. It's O(login). 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).

Upvotes: 1

Related Questions