Page 1 of 1

# Big O notation for a three dimensional loop

Posted 09 February 2019 - 06:22 AM

Hi,
I've been struggling with this calculation and I don't know how to continue and get the Big O complexity but I can only use summations Thank you, any help is really appreciated!
Is This A Good Question/Topic? 0

## Replies To: Big O notation for a three dimensional loop

### #2 Skydiver Reputation: 7132
• Posts: 24,226
• Joined: 05-May 12

## Re: Big O notation for a three dimensional loop

Posted 09 February 2019 - 08:01 AM

For just two nested loops, what is the big O? How did you get to that big O using summations?

The same principle will apply for three nested loops.

### #3 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12657
• Posts: 45,831
• Joined: 27-December 08

## Re: Big O notation for a three dimensional loop

Posted 09 February 2019 - 08:04 AM

Note that the summation over j takes i iterations, and you are adding (n-j+i) at each iteration. So break this apart into two summations:

\sum_{j=1}^{i} (n-j+1) = \sum_{j=1}^{i} (n+1) - \sum_{j=1}^{i} j
= i(n+1) - i(i+1)/2



Now you need to evaluate:
\sum_{i=1}^{n} [i(n+1) - i(i+1)/2]