# Big O notation for a three dimensional loop

Page 1 of 1

## 2 Replies - 347 Views - Last Post: 09 February 2019 - 08:04 AM

### #1 JackEsparrou

• New D.I.C Head

Reputation: 0
• Posts: 10
• Joined: 28-January 19

# 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

• Code herder

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]



You are welcome to keep asking about this, but please spend some time trying to make progress first!