5 ms·

(Warning: nerd sniping incoming) 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 cha

by roel_v 8y ago

(Warning: nerd sniping incoming) 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.)

worik 8y ago
...an algorithm or data structure operation described as being 'O(n)' could really be 'O(n) + x' 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.
- roel_v 8y ago
  Well yes, that's what I said, although I guess I could have used 'n + x operations' to keep it consistent with the article and still in line with the formal definition.
  - enedil 8y ago
    Yeah, you really could have. It also grinds me when people will say "it's O(n), not O(n^(3/2))", because the former is a subset of later, not to mention talking about worst case/average case/best case. Big O notation has nothing to do with probabilities, literally nothing.
opportune 8y ago
NO. BIG O notation is not average unless specified as such! It is an equivalence class of the provable upper bound on the execution time of the algorithm on an arbitrary input. There are algorithms like quick sort where average runtime != “big O of quicksort”
- roel_v 8y ago
  Sure that's what it is formally, but that's not the applied meaning the article is about. Take an hypothetical search algorithm that is O(1) except when the container you're searching is of length 50, then it's O(n). That makes the algorithm O(n), right? (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)
  - deleted 8y ago
    [deleted]
  - joshuamorton 8y ago
    No, that algorithm is O(1). 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).
    - roel_v 8y ago
      Yes you're right - let me modify my contrived example and say 'at exactly midnight, the complexity is O(n)'. (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 :) )
anon946 8y ago
Not only is 'O(n)' the same as 'O(n) + x', but also the same as 'c*O(n)', where c is a constant.
c3534l 8y ago
> 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). 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.
- teraflop 8y ago
  No, this is also inaccurate. Big-theta and average-case complexity are entirely different concepts. 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).
- edflsafoiewq 8y ago
  No, you're conflating Big O measuring an asymptotic upper bound of a function with worst-case analysis measuring the upper bound of resource use. These are different things. Asymptotic notation is totally oblivious to what is being measured, whether its a worst-case or average-case or anything else. You can give the Big O of the best case, the Big Theta of the worst case, etc.
- roel_v 8y ago
  Fair enough, when looking at the academic origin and defintions; but googling a bit and looking at articles like https://medium.com/@.RT/total-n00bs-guide-to-big-o-big-%CF%89-big-%CE%B8-aa259ae8a1c2 https://medium.com/@.RT/total-n00bs-guide-to-big-o-big-%CF%8... (under 'The Big Caveat', third paragraph), I feel validated in my assertion that your 'Big theta' is what is in practice and colloquially is known as 'Big O', and is also what this article is talking about. (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)
robconery 8y ago
OP here. Big O is indeed "worst case scenario" always, the size of the data set doesn't matter. An O(n) operation doesn't care if the data is sorted - even if it's the first item as you suggest. When you discuss Big O it's always worst case.
- kadoban 8y ago
  If Big O is always worst case, you're going to have a hard time saying anything interesting or useful about quicksort, for instance, or hash tables. 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.
- roel_v 8y ago
  Well that's not what your article is saying - it says (well, not in these words, but it's at least what I got from it) that it's meant to be something practical to understanding algorithmic complexity and how that relates to code performance. And for that, the size of the data and the details of the algorithm very much do matter. Throughout these comments, people seem to be using two 'concepts' of big O and because of that, talking past each other: the academic 'provable upper boundary' concept and the applied 'what algorithm or data structure should I choose for my concrete problem, and how does complexity help me decide' concept. That last one is what is colloquially known as 'big O analysis', whereas technically that term is reserved for something else indeed. I'll readily admit that when I first made my GP comment, I didn't really clearly make that distinction in my mind either, which is probably what is the real underlying issue I was trying to point out.
- UncleMeat 8y ago
  Big O is not "worst case scenario". It describes an upper bound on functions. You can absolutely compute the Big O of the average case runtime of an algorithm.
- umanwizard 8y ago
  This is wrong. Big-O can be used to talk about any function you like, whether best case of an algorithm, worst case, average case for uniform inputs, average case over some different distribution of inputs, how many branch mispredicts a Skylake core hits while running the code on backwards sorted input, the median price of a Big Mac as a function of a country's GDP per capita, or anything else.
eatbitseveryday 8y ago
>> "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, [...] 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.
- victorNicollet 8y ago
  I believe the point was that, if your linear search happens to return your first element, you did not perform 1000 operations. The context is a linear scan, not alternative algorithms that could make use of a sorted data set.
  - roel_v 8y ago
    Yes exactly.
LifeLiverTransp 8y ago
Also not mentioned, hardware pyramid makes fools of people who just expect the O-Notation to be the outcome of measured performance. A cache optimal - Algorithm thats worser in the 0-Notation might still outperform a bad implementation of a O-Notation superior algorithm. TL,DR; Knowing Big-O does not detach you from physics.
- hackerpacker 8y ago
  Nor the realities of various languages. I've seen hashes break down exponentially with "big data". (inb4 "then it wasn't a 'true' hash). There are countless variables beyond "+ x" If it is important, then you test/profile it. Otherwise it isn't important, and this is mostly theory crafting.
- mannykannot 8y ago
  This is an important consideration in practice, and I think it would be helpful if classes teaching O-notation would include an exercise that makes this point. It is also true, however, that O-notation considerations always dominate for large enough problems. 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).
- andreareina 8y ago
  And a lot of real-world implementations will use the asymptotically-inferior algorithm when the (sub)problem is small, for exactly this reason.
OrgNet 8y ago
in this context, n = n/2 ... because the performance difference is not that great.
mixmastamyk 8y ago
Good information for a part II blog post. Believe it makes sense to leave it out of the first.

by roel_v 8y ago

worik 8y ago

...an algorithm or data structure operation described as being 'O(n)' could really be 'O(n) + x' 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.

roel_v 8y ago
Well yes, that's what I said, although I guess I could have used 'n + x operations' to keep it consistent with the article and still in line with the formal definition.
- enedil 8y ago
  Yeah, you really could have. It also grinds me when people will say "it's O(n), not O(n^(3/2))", because the former is a subset of later, not to mention talking about worst case/average case/best case. Big O notation has nothing to do with probabilities, literally nothing.

opportune 8y ago

NO. BIG O notation is not average unless specified as such! It is an equivalence class of the provable upper bound on the execution time of the algorithm on an arbitrary input. There are algorithms like quick sort where average runtime != “big O of quicksort”

roel_v 8y ago
Sure that's what it is formally, but that's not the applied meaning the article is about. Take an hypothetical search algorithm that is O(1) except when the container you're searching is of length 50, then it's O(n). That makes the algorithm O(n), right? (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)
- deleted 8y ago
  [deleted]
- joshuamorton 8y ago
  No, that algorithm is O(1). 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).
  - roel_v 8y ago
    Yes you're right - let me modify my contrived example and say 'at exactly midnight, the complexity is O(n)'. (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 :) )

anon946 8y ago

Not only is 'O(n)' the same as 'O(n) + x', but also the same as 'c*O(n)', where c is a constant.

c3534l 8y ago

> 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). 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.

teraflop 8y ago
No, this is also inaccurate. Big-theta and average-case complexity are entirely different concepts. 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).
edflsafoiewq 8y ago
No, you're conflating Big O measuring an asymptotic upper bound of a function with worst-case analysis measuring the upper bound of resource use. These are different things. Asymptotic notation is totally oblivious to what is being measured, whether its a worst-case or average-case or anything else. You can give the Big O of the best case, the Big Theta of the worst case, etc.
roel_v 8y ago
Fair enough, when looking at the academic origin and defintions; but googling a bit and looking at articles like https://medium.com/@.RT/total-n00bs-guide-to-big-o-big-%CF%89-big-%CE%B8-aa259ae8a1c2 https://medium.com/@.RT/total-n00bs-guide-to-big-o-big-%CF%8... (under 'The Big Caveat', third paragraph), I feel validated in my assertion that your 'Big theta' is what is in practice and colloquially is known as 'Big O', and is also what this article is talking about. (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)

robconery 8y ago

OP here. Big O is indeed "worst case scenario" always, the size of the data set doesn't matter. An O(n) operation doesn't care if the data is sorted - even if it's the first item as you suggest. When you discuss Big O it's always worst case.

kadoban 8y ago
If Big O is always worst case, you're going to have a hard time saying anything interesting or useful about quicksort, for instance, or hash tables. 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.
roel_v 8y ago
Well that's not what your article is saying - it says (well, not in these words, but it's at least what I got from it) that it's meant to be something practical to understanding algorithmic complexity and how that relates to code performance. And for that, the size of the data and the details of the algorithm very much do matter. Throughout these comments, people seem to be using two 'concepts' of big O and because of that, talking past each other: the academic 'provable upper boundary' concept and the applied 'what algorithm or data structure should I choose for my concrete problem, and how does complexity help me decide' concept. That last one is what is colloquially known as 'big O analysis', whereas technically that term is reserved for something else indeed. I'll readily admit that when I first made my GP comment, I didn't really clearly make that distinction in my mind either, which is probably what is the real underlying issue I was trying to point out.
UncleMeat 8y ago
Big O is not "worst case scenario". It describes an upper bound on functions. You can absolutely compute the Big O of the average case runtime of an algorithm.
umanwizard 8y ago
This is wrong. Big-O can be used to talk about any function you like, whether best case of an algorithm, worst case, average case for uniform inputs, average case over some different distribution of inputs, how many branch mispredicts a Skylake core hits while running the code on backwards sorted input, the median price of a Big Mac as a function of a country's GDP per capita, or anything else.

eatbitseveryday 8y ago

>> "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, [...] 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.

victorNicollet 8y ago
I believe the point was that, if your linear search happens to return your first element, you did not perform 1000 operations. The context is a linear scan, not alternative algorithms that could make use of a sorted data set.
- roel_v 8y ago
  Yes exactly.

LifeLiverTransp 8y ago

Also not mentioned, hardware pyramid makes fools of people who just expect the O-Notation to be the outcome of measured performance. A cache optimal - Algorithm thats worser in the 0-Notation might still outperform a bad implementation of a O-Notation superior algorithm. TL,DR; Knowing Big-O does not detach you from physics.

hackerpacker 8y ago
Nor the realities of various languages. I've seen hashes break down exponentially with "big data". (inb4 "then it wasn't a 'true' hash). There are countless variables beyond "+ x" If it is important, then you test/profile it. Otherwise it isn't important, and this is mostly theory crafting.
mannykannot 8y ago
This is an important consideration in practice, and I think it would be helpful if classes teaching O-notation would include an exercise that makes this point. It is also true, however, that O-notation considerations always dominate for large enough problems. 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).
andreareina 8y ago
And a lot of real-world implementations will use the asymptotically-inferior algorithm when the (sub)problem is small, for exactly this reason.

OrgNet 8y ago

in this context, n = n/2 ... because the performance difference is not that great.

mixmastamyk 8y ago

Good information for a part II blog post. Believe it makes sense to leave it out of the first.