-1

Possible Duplicate:
Plain English explanation of Big O

I am reading an the " Introduction to Algorithms" Book, but dont understand this. O(100), O(log(n)), O(n*log(n)), O(n2), O(n3)

Ok Thanks, i dident even know what it was, so i am going to read that Big O post now. But if anyone can explain this any further in layman's terms it would be much appreciated.

Thanks

Community
  • 1
  • 1
lovetolearn
  • 93
  • 1
  • 4
  • 11
  • Try a google search for algorithm complexity. It gives about 36,100,000 results. The first couple should explain everything to you. In fact, the book you are reading, Cormen, Leiserson, Rivest, Stein right? It's own explanation should be good enough. I've read it, and can say its good. – darnir Nov 10 '11 at 09:39

2 Answers2

4

That is the big O notation and an order of efficiency of algorithms:

  • O(1), not O(100) - constant time - whatever the input, the algorithm executes in constant time

  • O(log(n)) - logarithmic time - as input gets larger, so will the time, but by a decreasing amount

  • O(n*log(n)) - linear * logarithmic - increases larger than linear, but not as fast as the following

  • O(n^2), or generally O(n^k) where k is a constant - polynomial time, probably the worst of feasible algorithms

There are worse algorithms, that are considered unfeasible for non-small inputs:

  • O(k^n) - exponential

  • O(n!) - factorial

  • Algorithms that follow an Ackerman function...

This notation is orientative. For example, some algorithms in O(n^2) can perform, on average, faster than O(n*log(n)) - see quicksort.

This notation is also an upper bound, meaning it describes a worst case scenario.

It can be used for space complexity or time complexity, where n is the size of the input provided.

svick
  • 236,525
  • 50
  • 385
  • 514
Luchian Grigore
  • 253,575
  • 64
  • 457
  • 625
  • Thanks so much i understand it alot better now, better explanation that any book i could have read. – lovetolearn Nov 10 '11 at 09:44
  • @JavaExpert you're far too kind :P – Luchian Grigore Nov 10 '11 at 09:45
  • There is no reason why you couldn't write O(100) to represent constant time. Although it's confusing, because the number has no meaning and it's not normally used. – svick Nov 10 '11 at 10:30
  • @svick O(1) is the standard notation, might as well use that. I doubt you'll find O(100) in any decent book, other than for stating it equals O(1). Thanks for the edit, the formatting is much better now. – Luchian Grigore Nov 10 '11 at 10:37
  • @LuchianGrigore I was wondering if there is an age which is too old or too late to start studying software engineering. For someone who has never coded before what would you say is the the latest age they should consider a career in software engineering. I would say there is no age limit you could be 100 but i dont think this is true with software. – lovetolearn Nov 10 '11 at 10:56
  • It depends on the employer... and the company. If the company's full of 20-something year-olds, a 50 year-old programmer might have trouble adapting. Other than that, I don't see why age would matter. – Luchian Grigore Nov 10 '11 at 11:04
1

Big O (simplifying) indicates how long will a given algorithm to complete, n being the amount of entry.

For example:

O(100) -> will take 100 units to complete no matter how much entry.

O(log(n)) -> will take log(n) to complete

O(n2) -> will take n^2 (n * n) to complete

m0skit0
  • 25,268
  • 11
  • 79
  • 127
  • "will take log(n) to complete" That's not exactly very clear... log(n) what? Seconds? Minutes? US$? – flight Nov 10 '11 at 09:39
  • Depends on what you want to measure (time, space...). – m0skit0 Nov 10 '11 at 09:42
  • O(log(n)) does not take log(n) time to complete. It simply states that as the input (n) gets larger, the output time increases by a factor of log(n). These values are not to be taken in their absolute sense. But instead they are used for relative comparisons. An algorithm whose running time increases as O(log(n)) is better than one that has a complexity of O(n). This was explained w.r.t. time. You may want to compute it w.r.t. memory or anything that you need. – darnir Nov 10 '11 at 09:44