I'm given the loop pseudocode:
where "to" is equivalent to "<="
sum = 0;
for i = 1 to n
for j = 1 to i^3
for k = 1 to j
sum++
I know the outermost loop runs n times.
Do the two inner loops also run n times though? (Making the entire Complexity O(n^3).
Where for instance n = 5 Then:
1 <= 5 2<= 5
j = 1 <= 1^3 2 <= 2^3 = 8
k=1 <= 1 2 <= 2
And this would continue n times for each loop, making it n^3?
This seems like a tricky problem, those inner loops are more complex than just n.
The outer loop is n.
The next loop goes to i^3. At the end of the outer loop i will be equal to n. This means that this loop at the end will be at n^3. Technically it would be (n^3)/2, but we ignore that since this is Big O.
The third loop goes to j, but at the end of the previous loop j will be equal to i^3. And we already determined that i^3 was equal to n^3.
So it looks like:
nn^3n^3Which looks like it comes to n^7. I'd want someone else to verify this though. Gotta love Big O.
You can use Sigma notation to explicitly unroll the number of basic operations in the loop (let sum++ be a basic operation):
Where
Hence, the complexity, using Big-O notation, is O(n^7).
