Big O Notation: Using not-boring math to measure code's efficiency
interviewcake.com
interviewcake.com
Many of the examples are wrong. A python "print" statement is (for the built-in types at least) O(n), so printing the first item from a list must be at least O(n).
Fundamentally, looking at big O notation as a way of measuring runtime is misguided. It is a way of describing a class of functions. But there is typically a level of indirection between the function that is being talked about, and the one which the analysis is applied to. For the "return the first item in the list" example, the function which is being analysed is a function from Int to Real. That function iterates through all values with size corresponding to the input to function, for each of these it runs the "return the first item in the list" function and measures the time it takes. The maximum time taken is then the Real output.
That intermediate function is important, and needs to be specified properly. If it isn't, then you get confusion The section "N could be the actual input, or the size of the input" is an example of this confusion. Here, the intermediate function which is being analysed is much simpler (but it is still present).
I should probably also add, that I am not by any means an expert here, and I wouldn't be surprised if I've made sloppy mistakes here. I'll just make the pre-claim that this only further proves my point that being hand-wavey is not a good thing :-)
The author does not state what his operations are. So, with regards to the examples, he implies that the operation he's counting is "print". So his examples are correct.
You are right, though, that we can get in trouble if it turns out that our base operation - which we assume is constant time - is actually not constant time. When looking at algorithms that deal with very large numbers, for example, we can't consider multiplication to be constant time.
So, with regards to the complexity of print, you are correct that it is linear - O(n) - in the item being printed. But I believe you are confusing the quantity "size of the list" and the quantity "size of an item in the list". If we have a list of size n, and that list contains items whose largest size is m, then we would say the cost of that first loop is O(n * m). If we can just assume that the size of an item is not large enough to matter - that is, m is actually a constant - then we can safely say that the cost is O(n).
Yes & no. Big-O is about counting something and seeing how that amount changes when our independent variable (input size, maybe) gets large. We can count whatever we want.
It is correct to say that
print(x)
> I don't think the attitude of being allowed to be hand-wavey is a good one for this sort of thing. Big O notation has very precise semantics, and it is very easily misused.
That's a good point. Perhaps the best way to present big-O for "the masses" is (1) give people enough guidance to use it correctly, (2) make sure they know that this is not hand-wavey math, but rather one with precise definitions, but (3) not worry so much whether they know what those definitions are, or how to use them directly.
http://stackoverflow.com/questions/471199/what-is-the-differ...
(Often, we are sure but we still use O.)
Big O tells you (to within some smaller order terms) how many more operations an algorithm needs to perform if you double the size of the input from really big to really, really big. This corresponds to increase in run time at small scale only if all else remains equal, which usually it doesn't. And even then, it only tells you the increase for that same algorithm, rather than how to compare the actual run time to other algorithms with different constants.
My hope is that someday Big O will be reserved for theory and programmers will preach something more like the roofline model: http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-13...
I do think it has one major omission -- something that is unfortunately omitted all too often. This is that, just as we get to decide what "n" means, we also get to decide what operations we are counting. Furthermore, our choices matter.
For example, if we are dealing with data accessed via a slow connection, or just about any kind of distributed system, operations that use the slow connection will be much slower than those that do not. So often we will count only those. O(n^2) doesn't give the full picture, if we only use O(n) slow operations.
For another example, if we are doing computations using large integers, then it usually does not make sense to count arithmetic operations as single operations. In such circumstances, a large-integer multiply can take a lot more time than a pointer dereference.
If you only look at the surface, and never care to think about what it's good for, mat can be quite boring.
Also how about a list of complexities in order of growth time?
Except big O notation is math and the use of it for complexity analysis is one application of it - this is a completely off-base statement.
First off, big O notation wasn't created with complexity theory or algorithms in mind. If I recall correctly, it has its roots in complex analysis. The notation was later borrowed as computational complexity was formalized. What happened is that people needed a way to describe the hardness or "logical sophistication" of problems and tasks. Looking into the asymptotic behavior of a complexity measure was just one means that they used. There are plenty of other ways to do this. The article reads like big O exists for the purpose of complexity analysis of algorithms. I doubt the author intended this, but they should be a bit more careful.
Time and space aren't the only resources of interest. Sometimes you need to quantify how much information you have or how much entropy there is. If you want to understand "what is basically happening", this is something you should pay attention to. Are we handling more information than we have to? What do we need and not need? Circuit sizes, sophistication of proofs, setups of databases, and the complexity of communications/protocols also play a role.
Even ignoring all this, the article is missing an elementary half of the picture: the structure of the input. It's not just about code and its design. Data structures matter, too. How information is organized, how it is encoded, and how it can be manipulated (computed on) makes an absolute huge difference. Are things sorted or unsorted? What kind of list or tree structure is your code working with? From what I understand, this is the whole point of a significant chunk of the interview questions candidates are presented with. It's ridiculous to omit this when introducing algorithmic complexity.
The author claims that Big O notation is an "awesome, not-boring kind of math where you get to wave your hands through the details and just focus on what's basically happening". They are hand waving not just the math, but also hand waving (and ignoring) most of the context as well. It doesn't even directly explain why big O notation models code efficiency in a fruitful way. It just mentions run time and memory usage superficially. In my opinion, this needs to be significantly revised or rewritten.
I see no problem with this. My first taste of algorithm analysis was in a freshmen year course, where we were taught the phrase "big oh" and how to analysis algorithms in quite a similar fashion as this article. The idea was to give us the briefest of introductions of the topic, just enough so we could talk intelligently about the elementary data structures we were being introduced to (vectors, lists, trees). We didn't get the real deal until senior year.
"Education is a series of small lies", is what my intro to computer engineering professor said when he said that, actually, some circuits are ternary, not binary.
Basically, the author is trying to introduce a concept to the reader. I don't fault him for not heaping the entirety of an area into an introduction.
If you fail to frame the context and the semantics well enough, you'll end up with people running around saying that an algorithm is "big O of blah." AGH
The introduction to the concept is articulated by the following comparison:
'We want to measure code efficiency. Big O notation describes this. Here are some examples.'
vs.
'We want to measure code efficiency. We can do this by thinking about its usage of resources (complexity). for example, total run time and memory usage. One of the ways to compare the efficiencies of algorithms is to compare their asymptotic behaviors. We can express this using big O notation. Here are some examples.'
-----
The author talks about how big O notation is awesome because you can drop the constants. It is not explained why this is awesome or useful. Interestingly, it later says that sometimes it isn't good because the constants sometimes matter. What is the reader supposed to understand here?
There's no followup as to what to think about after you determine the "big O" of an algorithm. Either he forgot to write this or figured that it was obvious at that point. Considering that he didn't sufficiently explain the concept's motivation either, I don't see how an uneducated reader will get a clear picture.
Those should really say θ(n) and θ(1).
Theta is the notation for a single case, be it the worst case, the best case, one run of a randomized algo, etc.
At least that is my understanding.