4 ms·

My favourite approach to big-O questions to to reply O(exp^n) to everything. When asked I point out that whatever it is, exp^n surely bounds it. This'll go eith

My favourite approach to big-O questions to to reply O(exp^n) to everything. When asked I point out that whatever it is, exp^n surely bounds it. This'll go either two ways. The interviewer will reflect on whether it is a least upper bound or not (and whether my statement is right) which makes for an interesting discussion about the other types of Landau notation. Or they'll get angry. Ultimately I'm not convinced based on my own personal experience that many of the people asking the question truly understand either. I see it in a somewhat negative light because I feel it is essentially a cargo culted interview technique - recite a few 0()s, yeah we all did CS degrees, great (or not). If you actually try to get into the weeds... I also don't think understanding big O notation is a great predictor of success of a software engineer. As well to ask if the series 1/n converges versus 1/n^2. What I'd rather see is that they can actually implement a solution. Take an ORM for example - a junior candidate knows how to use it and maybe how to debug it. A senior candidate might know that ORMs often emit very poorly optimised SQL and have some ideas on how to fix it. Example picked arbitrarily, ORMs aren't even my area. Even in my actual area of specialty the number of industry programmers who understand say what an elliptic curve with complex multiplication actually is, or even undergrad group theory, is quite limited. And they don't need to - I mean it is ideal if they do, but you can still implement ecc without much theoretical knowledge. There's also a bunch of "not academic" knowledge on various implementation techniques that academics might not know or care about. Brings me back to my ORM point. I'd much rather the person understands how the tools might fit together and more importantly learns any gaps or asks questions and identifies performance issues in the whole. That's not to say that time and space bounds don't matter. They do. But 99% of my use of this knowledge has been to answer interview questions.

yobbo 4y ago
It is an upper bound for something, but not the upper bound for that algorithm.
- 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 ago
    A 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 ago
    You 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 ago
    The 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.
dhd415 4y ago
I suspect that lots of people ask for O(n) when they mean Θ(n) instead which specifies both an upper and lower bound. For example, specifying Θ(n^3) as the running time for a bubble sort would be incorrect whereas O(n^3) would be imprecise but not incorrect.

yobbo 4y ago

It is an upper bound for something, but not the upper bound for that algorithm.

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 ago
  A 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 ago
  You 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 ago
  The 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.

dhd415 4y ago

I suspect that lots of people ask for O(n) when they mean Θ(n) instead which specifies both an upper and lower bound. For example, specifying Θ(n^3) as the running time for a bubble sort would be incorrect whereas O(n^3) would be imprecise but not incorrect.