CODEWITHSUNDEEP
loopsbig-otime-complexitycomplexity-theorydiscrete-mathematics
TOPKEK
TOPKEK

Reputation: 13

Finding the Complexity of Nested Loops

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?

Upvotes: 1

Views: 326

Answers (2)

dfrib
dfrib

Reputation: 73186

You can use Sigma notation to explicitly unroll the number of basic operations in the loop (let sum++ be a basic operation):

enter image description here

Where

Hence, the complexity, using Big-O notation, is O(n^7).

Upvotes: 0

Andrew_CS
Andrew_CS

Reputation: 2562

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:

  • 1st loop: n
  • 2nd loop: n^3
  • 3rd loop: n^3

Which looks like it comes to n^7. I'd want someone else to verify this though. Gotta love Big O.

Upvotes: 1

Related Questions