WTF Is Big O Notation?
rob.conery.io
rob.conery.io
The main problem with this article is that it doesn't stress (or even mention, as far as I can tell) that it's performance characteristics at the margins. Meaning, it's about a generalized operation on a very large data set. Your fancy hashing algorithm might be slower than just doing a linear scan over a 10-element table, not to mention the maintenance of your tree structure. In the article, this is most obvious in the following sentence:
"Let’s say we have 1000 records in our film table. To find “Academy Dinosaur” our database will need to do 1000 operations (comparing the title in each row)."
No you don't. If your table is sorted, you'll need only 1 operation to find 'Academy Dinosaur', because it's your first element. What does happen is that on average, to find any title, you will need n / 2 operations (so not 1000, but 500, in this example - this part is plain wrong as it's written). Of course, n / 2 is linear in n, so the complexity stays the same. But my point is that to understand big O notation for real world impact, you first need to understand the concepts the article mentions, and then you also need to be able to accurately assess the lower-dimensional terms that are left out, and estimate them.
(preempting counter sniping: this is assuming that titles are unique)
(to put this in other words, an algorithm or data structure operation described as being 'O(n)' could really be 'O(n) + x' where x is a constant; but we leave that out because at the margin, it doesn't matter (i.e. is dwarfed by the O(n) term. But when n is small and x is large, x becomes dominant, so assessing the effects of the complexity, in the real world, need to keep the expected magnitude of n in mind.)
No it should not. (O(N) + x) is O(N). That is how it works, is spoken about... What it means!
It is a very simple minded article, and IMO misleading, but it is better than "(O(N) + x) is bigger than O(N)". In the sense of order analysis, it is not.
(yes this is a stupid contrived example, and I know one can make any case when one can make up any reality etc. - but I think it's a valid style figure in this case, to contrast the theoretical definition with the application).
Would you toss out that search algorithm and say 'well we have algorithms that search in better than O(n) so forget about this one'? No, you'd do 'if (container.size() == 50) { return container.bisect_find(key); } else { container.lalaland_find(key); } And that's exactly the difference between the theoretical concept and the application.
(although I'll admit that I started out writing the comment trying really hard to avoid the word 'average' because it's so confusing and then it still slipped in)
50 is a constant. As n -> infinity, the algorithm runs in constant time.
Specifically, I can pick some number C such that C * f(n) > the number of operations, then the algorithm is O(f(n)).
So I choose f(n) == 1, and C == 100.
Then the runtime of the algorithm is 1,1,1,1,1...., 50,1,1,1,1,.... For all values of n, this is less than C * f(n) == 100, a constant, so it is O(f(n)). f(n) is 1, so it is O(1).
(the cool part about contrived examples is that you can keep making things up until it fits - now I'm just hoping I didn't miss something again like the first time :) )
(If you reject that and claim that just because I can construct an algorithm that is O(1) from yours doesn't mean that your algorithm is O(1), I'll point out what you presented isn't technically a function, since its not mathematically pure, so the concept of Big-O is ill-formed)
Also, I don't understand what you mean by 'mathematically pure', but that's on my end.
The other way is to ask "what is a function"?
Normally, a sorting function is expressed as
sort(List[Comparable]) -> List[Comparable]
sort(int, List[Comparable]) -> List[Comparable]
If the size of the int "time" is bounded (which it is, since the max is 86400), then one of the inputs is constant. It can be ignored.
Purity in this context is the idea that the function only acts on its inputs, there are no external forces that modify how it works. Pure functions are mathematical objects, impure functions aren't really.
So once you convert your construction to being pure, it becomes more clear why the function is ill-formed: you've got this extra constant size input (that runtime analysis can ignore) that you claim affects the runtime. Something is clearly amiss.
Each of those functions has its own big O, without specifying which function you are talking about big O isn't meaningful.
If someone asked "what is the runtime of quicksort in big O terms", it is ambiguous whether the answer is O(n^2) or O(n*log(n)) , since it's not clear which function you're talking about.
You're conflating theta and omega notation for big O. Big O is the worst case scenario. The average or even typical operation doesn't matter. If the algorithm is the most complex when sorting a list of items that were already sorted in descending order, then that is the use-case that is considered when figuring out Big O. If you want average, use Big theta.
Big-O/theta/omega are all ways of categorizing functions. Those functions typically take as their argument some measure of the "size" of the input (which may be one variable or multiple). The output of the function could be:
* worst-case performance ("largest possible running time for all inputs of size N")
* average-case performance ("expected running time for an input of size N, chosen from some well-defined distribution")
* amortized performance ("largest possible running time among all possible sequences of N inputs, divided by N")
(We could also apply any of these definitions to something other than time, such as memory or I/O operations.)
For any of these definitions, we can talk about big-O, or big-theta, or big-omega in a well-defined way.
As an example, the worst-case time complexity of bubble sort is Ɵ(n^2). The average-case time complexity (assuming an input consisting of distinct elements, uniformly randomly permuted) is also Ɵ(n^2). Nevertheless, the best-case performance is Ɵ(n).
(But I'll admit that I had mostly forgotten about this distinction, and certainly couldn't tell which one is which without looking it up)
For example:
Quicksort's average-case time complexity is Omega(1), also Omega(n log(n)), Theta(n log(n)), O(n log(n)), and also O(e^n).
Its worst-case time complexity is Omega(1), also Omega(n^2), Theta(n^2), O(n^2), and also O(e^n).
You're going to be limited to "quicksort is O(n^2)" and "hash table lookup is O(n)", both of which are quite misleading.
There are good reasons that we usually look at the worst case, but big-O does not fundamentally or necessarily mean that.
> No you don't. If your table is sorted, [...] on average, to find any title, you will need n / 2 operations (so not 1000, but 500, in this example - this part is plain wrong as it's written). Of course, n / 2 is linear in n, so the complexity stays the same.
If something is sorted, search happens in O(log N) which is not linear: start with compare at N'=N/2. If "less than", go to N''=N'/2; if "greater than" go to N''=3N'/2. Etc.
If the data is not sorted, then yes, you will need N lookup operations.
The context is a linear scan, not alternative algorithms that could make use of a sorted data set.
TL,DR; Knowing Big-O does not detach you from physics.
If it is important, then you test/profile it. Otherwise it isn't important, and this is mostly theory crafting.
Anyone expecting the O-Notation to give the outcome of measured performance has made a category error, as it is never about run-time itself, it is about the change of run-time with problem size (and only in the asymptopic limit).
I also find interviewers asking detailed questions about Big O and specific different algorithms just idiotic, especially the esoteric ones I've been asked in the past and/or heard asked. When I interview someone, all I want to know is that you know there is a difference and know to look when it matters.
My method for learning if a candidate understands this all is to get people to choose data structures based upon different problem sets I will give them and then ask the pros and cons. The more questions they ask about usage usually the more they understand in my experience. And this is just way more informative as a hiring manager as you will learn more if they understand what they are saying, versus if they can regurgitate something they memorized from a book or website.
I have sort of an intrinsic idea of what's going on -- self-joins can easily compare a data set with every other member of the data set, and hit O(N²). And that if your N is 5, the DB will probably going spend more time parsing SQL than executing your query, so no point in optimizing. So I don't understand or care about what the definition is, but it's useful tool to think about how slow your code can be.
Every theoretical model I've ever seen says that indexing into n bits of memory takes O(1) time. That's obviously impossible:
- The pointer you need to read is log(n) bits.
- The physical memory is at best O(n^(1/3)) distance away from the CPU, and thus takes that much time to get back to you. In reality it's probably O(n^(1/2)) because we build on flat planes (once you start talking about petabytes of data anyways).
Maybe this doesn't matter in practice, because the constants associated with these are small enough (but are they, how many memory/disk bound applications are there? How much extra performance could we squeeze out by using 16/32 bit pointers for small arrays?). It certainly doesn't matter in theory where things work like we say they do regardless of the physical reality. But it annoys me that it's so obviously wrong.
My googling dug up [1], but I'm not sure if that's it or not.
My university schooling was pretty straightforward about memory access not being O(1). We also went over adding two numbers together (also not O(1)), but these are just generally elided for brevity's sake; I don't think most of us want to start worrying/optimizing for CPU caches prior to it being a thing that perf testing says we need to worry about.
> 16/32 bit pointers for small arrays?
It's not about the size of the array, it's about the location in memory. If you're storing an index, then sure, knock yourself out.
[1]: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
¹I'm a software engineer, not a physicist.
That said, "time complexity" is a bit of a misnomer anyway. It's often implied, but underneath, there is a specific operation. For example, when we say that merge sort is O(N lg N), we mean in number of comparison operations.
Conversational Big O tends to include a lot of spherical cows (https://en.wikipedia.org/wiki/Spherical_cow), because when Big O comes up in conversation, people are more likely to be talking in generalities about high level designs. More detail could be counterproductive in that context.
When someone is actually trying to quantify and predict performance of an algorithm, then the other extreme becomes desirable- the more detailed and specific the function, the better.
With respect to the space problem, for some problems researchers don't care about it so much because it only means that it is a polynomial factor slower. For problems where the degree of the polynomial is important, theorists typically work with variants of Turing machines and need to specify which variant they are using, which typically do not allow random access, so this does not become important. Of course, random-access Turing machines are also studied that violate the physical constraint you mentioned.
(Hard to argue that this is related to big-O since there are only two data points, but I'm just pointing out that index size is in fact a real-world concern).
1. they are all fixed or bounded quantities;
2. all algorithms are subject to them.
On the other hand, in practice, the input size is also bounded. You deal not with arbitrarily long arrays, for example, since memory is not infinite.
So, I think, asymptotic time complexity is meaningful as long as the inputs we are considering can grow so much -- while remaining bounded -- that a linearithmic algorithm indeed outperforms, say, a quadratic one for a large and relevant class of inputs.
And that may be why computational models make those assumptions; but I'm not remotely sure.
A prime example, was a piece of code that has to process incoming results that get stuck in a transnational database table. Instead of selecting, then processing, the records that the module cares about, it does the selection (which typically returns 1 - 10 records), sorts them, processes the record from the top of the list, then throws the rest of the initial select results away. It then goes back to the DB an does the same select, and repeats the process.
End result: if the queue gets backed up to 100, or 1000 records, the process never catches up. You have to temporarily change the status of the inbound records to something else, then put maybe 10 at a time back to pending.
There are countless other times I've seen similar types of issues where on small data sets the code runs fine, but the performance degrades to n^2, or even worse is when it degrades in a factorial manor. And the worst of it is that if I talk to the developers using common CS notation (such as, your algorithm should have logarithmic or at worse linear degradation as the input queue grows, and it is behaving exponentially), their eyes glaze over.
Another recent example is a case where the app needed to start a number of sub-processes. So the dev used an equiv of a system() call, which spawned a bash shell, to do a ps -ef |grep process_name |grep -v grep |grep -v vi |grep -v vim |grep -v less, to see if the process was running, then doing another system() call to start the sub process. The whole string would be repeated for each sub process, and then they wondered why it took 8 minutes to start all their sub interfaces when they deployed to a larger customer that needed 700 interfaces started (instead of the typical 20 - 50). Oh, and after they would start an interface, the code would do the "ps..." commands on all the other interfaces to update an internal table on their status.
That's speaking as a professional. As someone who finds CS fascinating, I'm appalled by the lack of interest many professional developers have in what is one of the most rigorous and elegant fields of mathematical inquiry. Even so I don't expect others to care about the things I do.
This may be a case of the developers not understanding your ORM tooling. They get something that works, and don't quite what's going on under the hood.
Do you not hear people talk about 'accidentally quadratic' quite a bit? I hear practising developers talk about that a lot. They seem to have a good idea of what to avoid.
Do you mean that as in 'people I work with don't care about this, therefore it's not necessary' or as in 'people I work with are clowns who don't even know foundations'? Because (I think) I'm seeing replies to your post interpreting it both ways.
Nah it was just an expression from my part, didn't mean to say that anyone not thinking about algorithmic complexity when writing any piece of software is a hack :)
Sounds like a communication problem to me. Non-academic developers might not know "Big O notation". But they absolutely know that nested loops are way less efficient than single loops. They know that some code performs better than other code. And while they might be writing inefficient code, that is an opportunity to talk to them and help them improve.
If you come at them with academic terms (right though you may be), and their eyes glaze over, try talking about the actual change you are seeking. Especially in the database world, as less experienced developers might not know that database performance can be tuned by how you use it. We all were new once. So educate them. Kindly.
Every time I choose between a set and a vector in code, I'm essentially drawing on my knowledge of their big-O properties to choose the right one for whatever task I have at hand.
I wouldn't say that's the only piece of CS theory I use, either. I routinely run across problems that are best modeled as DAGs (any dependency relationship between items boils down to this quickly). I use DB theory any time I design a database table. I draw on language theory to write parsers.
Most of it is reflexive, I think, at this point, but it doesn't change that a "vector" is the right structure b/c I don't need O(1) lookup, or I'd like indexing.
This might potentially do someone a disservice. The whole point of analysis is just that - to "analyze" the runtime and not resort to "rules of thumb."
The presence of nested for loops itself is not a good reason to declare something quadratic. Consider the following which is most certainly not O(N^2):
for (int i = 0; i < 1000; i++)
for (int j = n; j >= 1; j = j / 2)
// do something
edit: you've now edited the inner loop to be n, but the outer loop is still 1000. This is still wrong, as the entire algorithm is now just O(lg n).
Also the fact that you're plugging numbers in for n indicates to me that you don't actually understand big O notation, which is surprising since the original article is decent.
[0] https://en.wikipedia.org/wiki/Big_O_notation#Formal_definiti...
That would be a sign that you as a candidate are being needlessly pedantic and usually a red flag.
Honestly it sounds as if you might not understand the difference between Theta and O. I understand that a function that is O(N^2) grows no faster than O(N^3) asymptotically speaking however the intention of my original comment and example is quite clear about their context.
Please stop, you are adding nothing to the discussion.
Maybe you might reread my original comment. This whole side discussion is of no value to my original comment which has a very clear and very narrow context.
I am not sure why the both of you want to belabor some ancillary talking point that you yourselves decided to introduce. It is of exactly no value to the context of my original comment and not in the least bit productive.
if for (int i = 0; i < 1000; i++) were instead
for (int i = 0; i < n; i++) - You'd have O(n)
If also for (int j = 1000; j >= 1; j = j / 2) were instead
for (int j = n; j >= 1; j = j / 2) - Then you'd have O(n log n)
OR for (int j = n; j >= 1; j -= 1) - O(n^2)
OR for (int j = n * 1000; j >= 1; j -= 1) - this is STILL O(n^2)
The thing is, I don't care about 'time complexity', I care about performance. Big O can serve as a useful datapoint for what the performance may be, but it's only that, one data point. e.g. It's not uncommon to find that a 'worse' algorithm/data structure in Big O terms will out perform a 'better' one because the 'worse' one has better cache locality. So no I don't think you should use an O(log n) operation in place of an O(n) operation just because of Big O, what matters is which one is faster.
>So no I don't think you should use an O(log n) operation in place of an O(n) operation just because of Big O, what matters is which one is faster.
Mathematically the log n is always faster :). Realistically... well that would be a tough one to prove, even with caching, but I say go for it.
By definition, they are not.
> Mathematically the log n is always faster :)
No, it's not. Time complexity only gives you an asymptotic bound on the number of 'operations', it tells you nothing about what the actual run time will be.
Mathematically, if n=1000 then log n is 10. 10 operations vs. 1000 is, theoretically and time complexity wise, faster.
Our disconnect is "actual" vs. "theoretical" and I want to stress again that Big O is purely theoretical. It's a technical adjective.
A function g(N) is said to be O(f(N)) if there exist constants c₀ and n₀ such that g(N) is less than c₀f(N) for all N > N₀.
Continuing: "Informally, this encapsulates the notion of “is proportional to” and frees the analyst from considering the details of particular machine characteristics. Furthermore, the statement that the running time of an algorithm is O(f(N)) is independent of the algorithm's input. Since we're interested in studying the algorithm, not the input or the implementation, the O-notation is a useful way to state upper bounds on running time which are independent of both inputs and implementation details."
I'll also repeat this bit from the end of the analysis chapter:
Perspective:
Many of the algorithms in this book have been subjected to detailed mathematical analysis and performance studies far too complex to be discussed here. Indeed, it is on the basis of such studies that we are able to recommend many of the algorithms we discuss.
Not all algorithms are worthy of such intense scrutiny; indeed during the design process, it is preferable to work with approximate performance indicators to guide the design process without extraneous detail. As the design becomes more refined, so must the analysis, and more sophisticated mathematical tools need to be applied. Often, the design process leads to detailed complexity studies that lead to "theoretical" algorithms rather far from any particular application. It is a common mistake to assume that rough analyses from complexity studies will translate immediately to efficient practical algorithms: this often leads to unpleasant surprises. On the other hand, computational complexity is a powerful tool for suggesting departures in design upon which important new methods can be based.
One should not use an algorithm without some indication of how it will perform. [...]
Doesn't provide the smug satisfaction of using the academic notation/jargon given in tech interviews and hn threads however.