Big-O Example

If you're like me you've seen the term "Big-O" but didn't quite grasp it the first time. You've also probably looked all over the Internet trying to make heads or tails of this seemingly complex term. If you weren't confused by the first definition that you found, try checking out the Wikipedia entry - that should get you nice and confused.

The purpose of Big-O notation is to provide a language that describes how efficient an algorithm is (or is not) without taking into consideration the exact speed of a particular computer that it might be running on. But how to calculate it?

Eventually I found a short mention of this topic in "Objects, Abstraction, Data Structures and Design using Java Version 5.0" by Elliot B. Koffman and Paul A.T. Wolfgang that seemed to make sense to me, and hopefully will click for you as well. The following was taken from pg113 Example 2.19:

Given T(n) = n² + 5n + 25, we want to show that this is indeed O(n²). Thus we want to show that there are constants n₀ and c such that for all n > n₀, cn² > n² + 5n + 25. To solve this we need to find a point where
cn2 = n2 + 5n + 25
If we let n be n₀ and solve for c, we get
c = 1 + 5/n0 + 25/n02
For an n₀ of 5, this gives us a c of 3. So 3n² > n² + 5n + 25 for all n greater than 5