Big O notation. Need help to explain the answers from the book?

Question

Hi, im having some problems understanding big o notation. My professor did a 1 day review, and our text book offers a 2 page blurp about it. However she has given us an assignment with a few questions on it(im not looking for answers to my homework, im simply wanting someone to explain the examples from my book) but i simply do not understand what to do to solve these problems, or what exactly they mean by their answers. Ill list a couple of examples from my book and hope you guys can help me understand what exactly is going on. This useless peice of junk that i wasted money on likes to simply give me the example and answer with no reasoning inbetween:

Examp: 3logn + 2 is O(log n)
Answer: <= 5log n for n >=1

Examp: 2n + 100log n is O(n)
Answer: <= 102n for n>=2

Examp: 2n is O(n!)


All my book simply says is that its easy to see the answer is blah blah........im just like no its not easy to see. Ive tried searching online for help but i find most sites have a different way of teaching it(one site simply took whatever was in the big O notation, and divided the equation by it and then got a number from it to use as c

http://www.cs.auckland.ac.nz/compsci220s...

thats the site that im talking about in case you dont know what i mean by the dividing by.......but anyways thats off topic since i would like someone to explain what exactly is going on if they could thanks

Answer 1

First of all, I would really advise you to get a better book, or try to find a better explanation on the web. http://www.amazon.com/Introduction-Design-Analysis-Algorithms-2nd/dp/0321358287/ref=pd_bbs_sr_3?ie=UTF8&s=books&qid=1221876499&sr=8-3 - my personal recommendation.



I will try to explain Big-O as simple as I can, but it is far from enough, you must find a resource for the study. Big-O simply shows how fast your algorithm will grow as you give it more input. It ignores the constants because it takes a limit as n -> infinity, in which case constants get dropped.



So something like 5n^2 - 1 is O(n^2)



Whenever you have function consisting of multiple variables with different orders of magnitude, you only take the one that is of higher order!



That is why 3n^2 + n - 5 is O(n^2) - n is of lower magnitude so drop it!



That is why in your 2n + 100log n is O(n), logs are of less magnitude.



That is as simple as I could be, check out the book on my link, it is great and gives a very thorough explanation of what Big-O is.

Answer 2

the 1st takes (a million/2)*n*n = a million/2(n^2) this is O(n^2). the 2nd, for every time via the outer loop, there are those numbers of operations for N = 32: 0 + a million + 2 + 2 + 3 + 3 + 3 + 3 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 in case you look, you have (a million/2)(a million x lg1 + 2 x lg2 + 4 x lg4 + 8 x lg8 + sixteen x lg16 + 32 x lg32) - so it seems O(Nlgn).

Answer 3

Big O notation is basically a "order of magnitude guesstimate" on the run time.



However, this "guesstimate" is only valid for "reasonable numbers".



In your first example, the function (3 log n + 2) has O (log n). Big O notation pretty much ignores constant multipliers and constants, as they don't affect the "order of magnitude" much. However, there's an implied range of valid numbers for the assumption to be true. In this case, n>=1



I also refer you to this PDF which should explain a bit more:



http://www.google.com/url?sa=t&source=web&ct=res&cd=1&url=http%3A%2F%2Fwww.collegeofidaho.edu%2Facademics%2Fmath%2Fcourses%2FCSC-140%2FPPTLectures%2FCh03_5AsymptoticNotation.ppt&ei=61jUSM6GE5mktQP7vsztDA&usg=AFQjCNGMuT222hzVpet4oLMwUpR8Mnlz5w&sig2=7jWJiL4Lxm05fdHUrz7Gtw