4 ms·
Big O, by definition, assumes as n -> ∞. This can be a really poor assumption in real world software that can bite both ways. Some "expensive" algorithms in te
by PheonixPharts 4y ago
Big O, by definition, assumes as n -> ∞.
This can be a really poor assumption in real world software that can bite both ways. Some "expensive" algorithms in terms of big O terms can be pretty efficient given real world data sizes. Additionally that C term that drops off at infinity can matter quite a lot if your real world problem size is small (meaning theoretically efficient algorithms can have a very high upfront cost).
Reasoning about actual runtime performance is far more important and intersects with the interesting/useful parts of computational complexity theory. Besides, in every interview I've been in they don't really mean "Big O", because I've never been required to produce a recurrence equation proving it, nor have I been confident the interviewer would even understand such an answer.
Understanding performance is hugely important in real world software, but Big O is a tiny part of that in practice.
- charcircuit 4y agoYou don't need a recurrence relation to prove it. You can use a simple algebra where you are able to combine the complexing of algorithms. For example an O(n) algorithm followed by an O(n^2) algorithm will be O(n^2). In an interview I describe how the complexity of these simpler algorithms get combined into my final answer. I assume that the interviewer and I can agree on some basic stuff like looping over an array is O(n), inserting into a heap is O(log(n)), etc.