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

#1 JackEsparrou   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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

Posted Image

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   User is offline

  • Code herder
  • member icon

Reputation: 7132
  • View blog
  • 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.
Was This Post Helpful? 1
  • +
  • -

#3 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12657
  • View blog
  • 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!
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1