Menu
I want to calculate the theta complexity of this nested for loop:
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
for (int k = 0; k < j; k++) {
// statement
I'd say it's n^3, but I don't think this is correct, because each for loop does not go from 1 to n. I did some tests:
n = 5 -> 10
10 -> 120
30 -> 4060
50 -> 19600
So it must be between n^2 and n^3. I tried the summation formula and such, but my results are way too high. Though of n^2 log(n), but that's also wrong...
334
O(nc): Time complexity of nested loops is equal to the number of times the innermost statement is executed. An algorithm with three-nested loops will have O(n3)
Nested iterations are not necessarily a bad thing. Even many well-known algorithms rely on them. But you have to be extremely cautious what you execute in the deepest loop, since these commands will be performed very often.
The outer loop executes 2 times and each time the outer loop executes the inner loop executes 3 times so this will print 2 * 3 = 6 stars. The formula for calculating the number of times the inner loop executes is the number of times the outer loop repeats multiplied by the number of times the inner loop repeats.
Asymptotic analysis refers to computing the running time of any operation in mathematical units of computation. In Asymptotic Analysis, the performance of an algorithm in terms of input size (we don't measure the actual running time) is evaluated.
Using Sigma Notation is an efficient step by step methodology:
181
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
