开发者

Big Oh Notation and Calculating the Running Time for a Triple-Nested For-Loop

开发者 https://www.devze.com 2023-02-07 05:48 出处:网络
In Computer Science, it is very important for Computer Scientists to know how to calculate the running times of algorithms in order to optimize code. For you Computer Scientists, I pose a question.

In Computer Science, it is very important for Computer Scientists to know how to calculate the running times of algorithms in order to optimize code. For you Computer Scientists, I pose a question.

I understand that, in terms of n, a double-nested for-loop typically has a running time of n2 and a triple-nested for-loop typically has a running time of n3.

However, for a case where the code looks like this, would the running time be n4?

x = 0;
for(a = 0; a < n; a++)
    for(b = 0; b < 2a; b++)
        for (c=0; c < b*b; c++)
            x++;

I simplified the running time for each line to be virtually (n+1) for the first loop, (2n+1) for the second loop, and (2n)2+1 for the third loop. Assuming the terms are multiplied together, and we extract the hi开发者_如何转开发ghest term to find the Big Oh, would the running time be n4, or would it still follow the usual running-time of n3?

I would appreciate any input. Thank you very much in advance.


You are correct, n*2n*4n2 = O(n4).

The triple nested loop only means there will be three numbers to multiply to determine the final Big O - each multiplicand itself is dependent on how much "processing" each loop does though.

In your case the first loop does O(n) operations, the second one O(2n) = O(n) and the inner loop does O(n2) operations, so overall O(n*n*n2) = O(n4).


Formally, using Sigma Notation, you can obtain this:

Big Oh Notation and Calculating the Running Time for a Triple-Nested For-Loop


Could this be a question for Mathematics?

My gut feelings, like BrokenGlass is that it is O(n⁴).

EDIT: Sum of squares and Sum of cubes give a pretty good understanding of what is involved. The answer is a resounding O(n^4): sum(a=0 to n) of (sum(b=0 to 2a) of (b^2)). The inner sum is congruent to a^3. Therefore your outer sum is congruent to n^4.

Pity, I thought you might get away with some log instead of n^4. Never mind.

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号