Big Oh Notation and Runtime Computation for Triple-Nested for-Loop

Question

In the field of computer science, it is very important that computer scientists know how to calculate the running time of algorithms to optimize code. For you computer scientists, I ask a question.

I understand that in terms of n, a double nested for-loop usually has a run time of n ² and a triple nested for-loop usually has a run time of n ³ .

However, for the case where the code looks like this, will the runtime 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 run time for each row to be practically (n + 1) for the first cycle, (2n + 1) for the second cycle, and (2n) ² +1 for the third cycle. Assuming the members are multiplied together and we extract the highest term to search for Big Oh, whether the run time is n ⁴ or will it still follow the normal time n ³

I would be grateful for any input. Thank you so much in advance.

Answer 1

You are right, n * 2n * 4n ² = O (n ⁴ ).

A triple nested loop means that to determine the final Big O, three numbers will be multiplied, each of which will depend on how much “processing” each cycle does.

In your case, the first loop performs the operations O (n), the second O (2n) = O (n), and the inner loop performs the operations O (n ² ), so the total O (n * n * n ² ) = O (n ⁴ )

Answer 2

Formally, using Sigma Notation, you can get the following:

Answer 3

Could this be a question for Mathematics ?

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

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

Sorry, I thought you could leave with some kind of magazine instead of n ^ 4. Nothing.