• Post Reply Bookmark Topic Watch Topic
  • New Topic

Big O  RSS feed

 
Brian King
Ranch Hand
Posts: 35
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

I'm currently reading about algorithms and have come across Big-O and calculating the time it takes various algorithms to run.  I'm getting to a point where I'm seeing problems like the one below and genuinely have no idea what I'm looking at or how to solve it.  I know the answer to the below problem is O((4N3 + 27N2 + 53N + 12)/6) but I have no idea why.  Does anyone recommend any books, websites, or what not that will explain stuff like this step-by-step?  It's really bothering me but I just don't see the pattern or whatever will help me solve these better.

Thanks,
Brian

Determine the precise (i.e., not just the order of magnitude) Big-Oh values for the following code sample, based on the number of statement executions, as described in the Module 1 lecture. Choose the answer that best agrees with the value you have determined. Keep the following considerations in mind:

•    Remember to consider each statement in compound statements separately.
•    Pay close attention to the initial and end values of loop variables!
•    Loops such as "for" and "while" contain an implicit "jump" instruction that causes execution to proceed from the end of the loop back to the beginning of the loop.

Code sample:



 
Pete Letkeman
Ranch Foreman
Posts: 901
26
Android Chrome IntelliJ IDE Java MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Brian King wrote:reading about algorithms and have come across Big-O and calculating the time it takes various algorithms to run.

I foundfind this topic interesting, but that could be because I know fairly little about it.

I'm not too sure if this helps but there are some resources listed here
https://coderanch.com/c/books

Edit: Grammar Fixed
 
Campbell Ritchie
Marshal
Posts: 56533
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Brian King wrote:. . . the answer to the below problem is O((4N3 + 27N2 + 53N + 12)/6) but I have no idea why. . . .
But that isn't the correct big O value. The correct value is O(n³)

The outer loop runs n×
The middle loop runs n, n − 1, n − 2, n − 3, n − 4, n − 5, × The fewest number of times it can run is 0; for some peculiar reason it has never been possible to make a loop run a negative number of times What you have above is an arithmetic progression (=AP), and you know the sum of an arithmetic progression is (n₀ + nₙ) × m ÷ 2. Now, in an AP starting 0 whose numbers differ by 1, you multiply n by (n + 1) and halve it. Note that is the same as (n² + n) ÷ 2. Now multiply that by n for the outer loop. For the inner loop you are going to have the same rigmarole for each of the loops. The bit about sum += j; is really easy by comparison: addition runs in constant time =O(1).

Please always tell us where such questions come from, to avoid copyright problems and in this case, so we know to avoid it.

Also, is there any n such that 4n³ + 27n² + 53n doesn't divide by six? No, I think it will always divide by six.

I am not convinced you will understand the Wikipedia page. I did a search and this looks a good link.
 
Stephan van Hulst
Saloon Keeper
Posts: 7969
143
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Brian King wrote:Determine the precise (i.e., not just the order of magnitude) Big-Oh value

This doesn't make sense. The very definition of Big-Oh relates only to order of magnitude. O((4*n^3 + 27*n^2 + 53*n + 12)/6) doesn't actually mean anything more than O(n^3). Whoever asked the question just wants to know a formula for the number of times the sum += j; is executed.
 
Brian King
Ranch Hand
Posts: 35
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Oh, sorry.  It's from an online course, not a specific book.  I actually put N^3 as the answer but got it wrong, as I did with every other problem like it.  But yeah, I guess it's summing each term and I'm confused how to do that. For example, this is number six of thirteen steps 
given for arriving at O((4N3 + 27N2 + 53N + 12)/6):


Statement# of times executed (general)actual # of times executed (N = 10)Comments
k < n;N(N + 1)(N + 2)/6 + N(N + 1)/2275This conditional statement is nested at the 3rd level. Since the value of k is dependent on the current value of j, and the value of j is dependent on the current value of i, the base number of executions is given by the 3rd figurate number formula: N(N + 1)(N + 2)/6. However, since this is a loop termination condition, it must also be executed an additional time for every iteration of the enclosing j loop, so the total number of executions will be N(N + 1)(N + 2)/6 + N(N + 1)/2.


 
Brian King
Ranch Hand
Posts: 35
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the replies everyone.  I think you're right Campbell Ritchie where I'm struggling with how to determine complexities.  Going to print out what you recommended and hopefully understand it: )
 
Campbell Ritchie
Marshal
Posts: 56533
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Brian King wrote:. . .  It's from an online course . . .
Please tell us which course. I hope you aren't paying much for it.
 
Brian King
Ranch Hand
Posts: 35
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
lol...it's called Data Structures and Algorithms and I'm taking it online through University of Illinois.  It's more just for fun (I'm already an adult with a job and all that nonsense) but I get really frustrated and obsessed when I can't understand something.  The professor is very nice and responsive but I sort of feel like maybe I'm missing huge chunks of background knowledge not knowing the answers to questions like the above.
 
Campbell Ritchie
Marshal
Posts: 56533
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am surprised they made a mistake like that; maybe that is the only mistake and the rest of the course is correct.

There is nothing wrong with learning something for fun and improving your mind
 
Brian King
Ranch Hand
Posts: 35
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sorry if I'm being annoying about this.  Does anyone happen to know of any videos that go over determining complexity or maybe a site where you can practice with immediate feedback (sort of like Khan Academy)?
 
Pete Letkeman
Ranch Foreman
Posts: 901
26
Android Chrome IntelliJ IDE Java MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Brian have you tried Khan Academy?
https://www.khanacademy.org/computing/computer-science/algorithms wrote:Asymptotic notation

Learn how to use asymptotic analysis to describe the efficiency of an algorithm, and how to use asymptotic notation (Big O, Big-Theta, and Big-Omega) to more precisely describe the efficiency.
 
Campbell Ritchie
Marshal
Posts: 56533
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Brian King wrote:Sorry if I'm being annoying about this.
You're not being annoying. There's nothing to apologise about.
Does anyone happen to know . . .?
'Fraid not myself, but other people do (thank you PK).
 
Brian King
Ranch Hand
Posts: 35
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks again. I'm actually going through Khan Academy but still on the binary search part.  Think I'm probably biting off more than I can chew and don't have time to squeeze everything in.

Thanks for all the help.  You guys/gals are awesome.
 
Punit Jain
Ranch Hand
Posts: 1085
3
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Try "Cracking the Coding Interview: 189 Programming Questions and Solutions."

Also, this video: https://www.youtube.com/watch?v=v4cd1O4zkGw&t=154s
 
Brian King
Ranch Hand
Posts: 35
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!