7 ms·
This is a common misunderstanding of computational complexity: It does not measure runtime, but how runtime changes depending on the input. Take the following
by Sebb767 4y ago
This is a common misunderstanding of computational complexity: It does not measure runtime, but how runtime changes depending on the input. Take the following two algorithms to find the square root of an int:
result=None
for i in 0...INT_MAX
if i*i==searched
result=i
return i
and
for i in 0...searched
if i*i==searched
return i
The first algorithm is O(1), the second is O(sqrt(searched)). Despite this, the second will clearly be faster in actual execution time. However, if your number range changes from 0-100 to 100,000,000-250,000,000 , the former will still take the same time while the latter will take a lot longer. Now, in this example, this is quite obvious, but in the real world, you might encounter cases where a quadratic complexity solution is completely fine, until you have a lot of data and then suddenly your code slows to a crawl [0]. That's why we need computational complexity - it was never designed to perfectly measure or predict execution speed. This is also the reason constants are dropped in the notation.
For real world performance, benchmarking is the key. Computers are very complex beasts and there are a lot of potential speedups or slowdowns you might never think of - memory bank order, thermal throttling and compiler optimizability can drastically change the results, just to name a few. Computational complexity is totally fine as an angle to find new possible optimizations, but in the end, you need to compare it to the other approaches and see what actually works.
[0] https://news.ycombinator.com/item?id=21743424 https://news.ycombinator.com/item?id=21743424
- mining 4y agoI would probably argue that either the first algorithm is incorrect (because searched can be larger than INT_MAX) or the complexity of the second algorithm is bound both by O(searched) (or sqrt(searched), if implemented with more vigour) and O(1) (because the value of 'searched' is bound by a constant).
- Sebb767 4y agoI explicitly wrote > to find the square root of an int: so the value can't exceed INT_MAX :) Overall, I know the two algorithms aren't perfect, but they're a simple minimal example to show the difference between complexity and runtime.
- ChrisLomont 4y agoYou cannot talk about complexity without letting n-> infinity. Both algorithms are O(1), since n is bounded.
- Sebb767 4y agoTrue, but I wanted to go with a simple example to show my point.
- waynesonfire 4y agohow is n bounded in the 2nd algorithm?
- xigoi 4y agoIf you assume that it's unbounded, then either the algorithms aren't solving the same problem or the first one is wrong, so it doesn't make sense to compare them.
- amag 4y ago> For real world performance, benchmarking is the key. Only it's not enough. When you benchmark an O(N^2) algo may seem fine but then three years later the data has changed and is now an order of magnitude larger. So you need not only know your data, you also need to spend time thinking about how large it can become.
- Ozzie_osman 4y agoThat's the point of O-notation though. It helps you know how your computation will degrade as your data grows. So you start with benchmarking your current data. You still need to always think about how your data will grow.
- inetknght 4y ago> Only it's not enough. True. But I do highly recommend watching Ben Deane's 2015 talk about testing Battle.net. In it he briefly touches upon benchmarks and estimating algorithmic complexity. It's somewhat difficult to suss-out the details of it. But the short version is basically to run the benchmark with a few different sizes and then estimate the complexity growth from that. https://youtu.be/OPoZWnYIcP4?t=1035 https://youtu.be/OPoZWnYIcP4?t=1035
- robby_w_g 4y ago> When you benchmark an O(N^2) algo may seem fine but then three years later the data has changed and is now an order of magnitude larger The GTA Online loading screen bug is a recent example of this problem, with its in-game purchasable items growing larger over time: https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times-by-70/ https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times...
- deleted 4y ago[deleted]
- quietbritishjim 4y agoYou seem to be agreeing with the parent comment's point. For example, there's this bit of their comment, which is almost verbatim what you replied back with: > ... you might encounter cases where a quadratic complexity solution is completely fine, until you have a lot of data and then suddenly your code slows to a crawl [0]. That's why we need computational complexity ... It seems like you're disagreeing only because you pulled out the one quote about benchmarking. But they were just saying that you need benchmarking to bootstrap the meaning of O(...) of an algorithm. That's the point that the original article missed, which is presumably why they described it as key.
- ralusek 4y agoI would have a huge problem describing the first one as O(1). Technically the complexity is min(searched, INT_MAX), but the algorithm would also fail to produce a result if it reaches INT_MAX. Functionally, though, I would describe this algorithm as O(N). It's just a straight up linear scan of the problem space. It's unbounded, with a worst case of O(Infinity) and no upper limit on what searched can be, but it's functionally O(N) regardless. O(1) needs to basically be something like a hash key/pointer to memory address to get the result you're looking for. It will not increase linearly as the problem space increases, whereas your first example increases exactly linearly.
- devmop 4y agoIt takes the same (huge) amount of time for all inputs - there's no early exit it always scans to INT_MAX. Hence O(1)
- glitchc 4y agoThis is incorrect. Putting a finite bound on n does not reduce n to 1. n is always meant to be a finite arbitrarily large value. n=INT_MAX qualifies as arbitrarily large, especially on a 64-bit system.
- carnitine 4y agoO(x) = O(1) if x is some finite constant.
- PhineasRex 4y agoThere is no bound on n, it always searches to INT_MAX regardless of n.
- Sohcahtoa82 4y agoBig-O notation says nothing about the overall absolute size. All that matters is how the amount of work scales with the input value. If an algorithm will always take 1 billion years to complete regardless of the input, then it's still O(1).
- finalfire 4y agoQuestion: is the first algorithm O(1) cause we treat INT_MAX as a constant, right?
- 1270018080 4y agoCorrect.
- pjungwir 4y agoIt looks like you intended your first snippet to end with `return result` not `return i`, right? Mixing real-machine finitude with big-O theory often gives unexpected or unhelpful results. Once in an interview I argued that since hash tables have a finite number of buckets, at large enough scale they really have O(n) worse-case performance. That didn't go over very well. :-)