4 ms·
Told you it drives people nuts. So big-O implies that the runtime is "dominated" by the term in brackets, or put another way, if I say something is O(n^2) I'm
by zahllos 4y ago
Told you it drives people nuts.
So big-O implies that the runtime is "dominated" by the term in brackets, or put another way, if I say something is O(n^2) I'm stating that as n->infinity the runtime of the algorithm |R| <= c * n^2, where c is some constant.
This is still true of exp^n, since |R| <= cn^2 <= dexp^n. Or at least based on my analysis background I'd expect this behaviour. It is of course a little pointless to say the algorithm is O(exp^n), but that's a different issue. It is still an asymptotic upper bound.
I just checked my copy of Sipser. Example 7.3 on page 249 if you care. They give an example that f_1 is O(n^3) and state it is O(n^4) also, since n^4 is also an (asymptotic bound) bound.
But this is not the point. I have no formal computer science education at all (my background is mathematics, some logic if that counts, but I've never studied algorithms) but many interviewers insist on this one specific area of CS, and yet if you attempt to engage them on the meaning of the things then unless you are very lucky they will a) make some excuse about how they'd have to check, their degree is a while ago, or b) they're actually only reciting also.
I'm strongly of the view this is a massively cargo-culted interview question of questionable to no value for most software engineering jobs, given that interview time is very limited and there are many more important factors to evaluate.
- randomtwiddler 4y agoA follow up. I'm more interested in a devs understanding of memory complexity than time complexity. Every single production performance issue I've seen out side of academic questions had been due to memory management issues.
- randomtwiddler 4y agoYou seem to be missing the entire point of this kind of question. Yes, you are providing an upper bound. But as you yourself admit, your answer is useless. The point of big o is to put the lowest reasonable bound on an algorithm so they can be compared. Your approach is basically interview trolling. I don't use big o in interviews. That's more the domain of big data than the web slots I typically fill. I'm more interested in the depth of understanding they display in the techs they claim to know.
- Falkon1313 4y ago
- yobbo 4y agoThe complexity bound of an algorithm is the worst possible complexity. It needs to be proven (by assuming the worst possible input data), and there exists only one provable bound for a particular algorithm. Finding the complexity of an algorithm in school is an exercise for understanding algorithms, and gaining a "vocabulary" for talking about them. But, provable bounds don't correspond to practical bounds, since input data is almost never close to the worst-case scenario. It isn't really a practical skill. Several algorithms have bad provable complexity but can perform well in practice, while algorithms with better provable complexity can perform worse on average input sets.