Beginner Java student: Big-Oh Notation?
I don't know what happened, but I completely understood the concept of big-oh notation in the lecture, but when I read it again in the textbook, I got lost. Here is what my textbook says:
Q(1)
"In general, O(f(n)) means that the quantity being measured is at most c X f(n) for some constant c."
Whoa, I got how thelinear search example of searching an array for a minimum by going through all the elements to the end would be considered O(n). But now f(n)? Maybe that makes sense where, log(n), n, 2n, 3n, n^2 and such are all 'functions' of n. But in that case I don't see where the constant c comes from. What do they mean by the constant c? f(n) already represents every possible thing you can do to n.
-
Q(2)
"When we convert an expression that involved several terms into big-oh notation, only the fastest growing term remains. For example, 3n^2 + 20n + 15 is O(n^2) because c X n^2 is larger than 3n^2 + 20n + 15 for all values of n greater than 3, if c = 10"
What the HELL? Now I don't even see how a polynomial expression of n relates to the processing of an array in java. How does this relate to the amount of times you search through an array or go through a loop? Furthermore, why would any vaue of n be greater than 3? The c in c X n^2 is what seems to correlate with the 3 in the expression. Not the n. Why would you go into picking an arbitrary number for n? Then, why the hell would c be 10? Why 10? f you plug in 10, WHAT RELEVANCE does that result have on anything? aahh
aahh I'm taking calculus next year, I can't believe how much the math part of my brain has deteriorated since high school..
Message was edited by:
lk@ucsc
Message was edited by:
lk@ucsc
[1784 byte] By [
lk@ucsca] at [2007-11-27 5:33:27]
# 1
> Here is what my textbook says:
>
> Q(1)
> "In general, O(f(n)) means that the quantity being measured is at most c X f(n) for some constant c."
> Maybe that makes sense where, log(n), n, 2n, 3n, n^2 and such are all 'functions' of n.
Yes
> But in that case I don't see where the constant c comes from.
Well, if my computer's twice as fast as yours, then if you're measuring speed, my value of c will be half yours, but the way a given algorithm scales will still be O(f(n)).
> f(n) already represents every possible thing you can do to n.
True, but the constant lets you use the simplest f(n) - you can say 'this algorithm scales as O(n^2 ln n)' rather than 'the scaling of a specific implementation of this algorithm is bounded above by 500 n^2 ln n ms on a AMD 3400 powered notebook'
>
> Q(2)
> "When we convert an expression that involved several terms into big-oh notation, only the fastest growing term remains. For example, 3n^2 + 20n + 15 is O(n^2) because c X n^2 is larger than 3n^2 + 20n + 15 for all values of n greater than 3, if c = 10"
>
> What the HELL?
> Now I don't even see how a polynomial expression of n relates to the processing of an array in java.
Most simple looping over arrays in Java are O(n). This is talking about things with are not O(n), so it doesn't relate to looping over an array in Java. On the other hand, if you are comparing every element in the array to each other, you make n(n-1)/2 comparisons so you would get a polynomial number of operations with an array.
>How does this relate to the amount of times you search through an array or go through a loop?
A single loop is usually O(n), two nested loops would usually be O(n^2), and so on. A divide-and-conquer approach such as merge sort where you recursively process half the data would usually be O(ln n).
> Furthermore, why would any vaue of n be greater than 3? The c in c X n^2 is what seems to correlate with the 3 in the expression. Not the n.
Yes, for sufficiently large n, 3n^2 + 20n + 15 ~= C n^2, where C = 3.
For any value of C>3, there will be a value n_1 where f(n)<C n^2 for all n > n_1, which can be derived from (C-3)n^2>20n+15.
Therefore 3n^2 + 20n + 15 is O(n^2).
Setting C to 10 so n is 'sufficiently large' at 3 without saying why is a bit poor, but a full treatment requires some background on limits and bounds of series, which requires some calculus....
> aahh I'm taking calculus next year, I can't believe how much the math part of my brain has deteriorated since high school..
Neither of your questions are anything to do with math, just the way it's been illustrated, and maybe the order you're being taught in.
Pete
# 2
I got stuck learning this in my first year of college.
The basic concept of big-Oh notation is all about approximation. I think that's what confused me, since all of the previous math i had learned was very exact. Big oh is just a formal way of saying "it's about this efficient".
Lets say that you come up with a sorting algorithm that sorts n elements. If you need to do g(n) = 3n^2+20n+15 comparisons to perform that sorting, you have a quality measure of the algorithm.
Now, if you are to consider how good this algo is on sorting really big arrays, you are looking at really big n. When n is large, 3*n^2 is going to be several magnitudes larger than just 20*n, and 15 is going to be ridiculously small in comparison.
If you think about it, all you really need to know when n is getting large, is whether you've got something in the magnitude of n^3, n^2 or n, since n^3 is almost always larger than any constant times n^2 (for sufficiently large n that is, the basic idea is that n^3 increases much faster than n^2).
So you categorize your algorithms in there growth speed (if you double the input size, how much longer / much more memory / more disk space / is it going to consume?).
So in your example, 3*n^2 easily wins since it grows much faster that 20*n or 15 (15 doesn't grow at all). You then make the approximation that 20*n doesn't matter since you're dealing with large n and 20*n is going to be insignificantly small when n is large. 15 is negligible. You then scrap the scaling number three in front of n^2, even though its kinda important. This is to narrow down the categories. You don't make a difference between 3*n^2 and 20*n^2, since when n is very big, both of these are going to be outperforming n^3-algos anyway...
The formal definition of this "approximation" is that
"The algo is O(f(n)) ("is in the order of f(n)") if it is bounded by c*f(n)". Think about it, it's very logical. It's just saying that O(n^2)-functions can never get near O(n^3)-functions, but they may still vary quite widely in performance.
Note that f(n) is not a general function, it is _fixed_ for the specific category.
For linear algos, f(n)=n. For quadratic algos, f(n)=n^2 etc... See http://en.wikipedia.org/wiki/Big_O_notation#Common_orders_of_functions
Hope this sorts things out for you...
# 3
At an intuitive level, saying O(cn) is the same as O(n) is really just saying that in calculating the time complexity, we don't consider things that don't increase with the input size. The other reason is that I might have a loop with 4 method calls in it and you might have an equivalent loop that has 2 method calls in it. If we count yours as O(2n) and mine as O(4n) you might say yours is faster. But then I would turn around and say that your two methods each call 15 other methods and mine only each call 5 methods and therefore yours is O(30n) and mine is O(20n). Then you look at the bytecodes generated by my code and the bytcodes generated by yours and say yours is O(50n) and mine is O(100n). Then I look at the machine code that the VM produces etc...
These constants will have an effect on real performance as long as the constant c is comparable to n, but for the purposes of time complexity, they are not useful. Where you are going with time complexity will be things like whether a given problem is in certain classes of 'unsolvable' problems.
In terms of practical use, it helps you to understand how an algorithm will perform under greater and greater loads. It's wise to avoid n?algorithms (like bubble sort) because they will seem to work OK (maybe even faster than the alternatives) until your N starts to grow and then they will be dogs. If your code has exponential complexity, you can almost guarantee big problems will come.
