3 ms·

Is O(n + log n) really a thing or should he just write O(n)?

• Spivak 6y ago
  Short answer is no because we’re talking about asymptotic behavior and n dominates log n. Long answer is yes because O notation is commonly written this way to be more illustrative of what’s happening in an algorithm and that were smushing to algorithms together. If you can be more precise then feel free to write it down. For example O notation hides a constant factor but if you happen to actually know it exactly you might see O(7n) in the wild.
• kaunta 6y ago
  I should just write O(n). Thanks for catching the mistake, @dmurray. I'll fix that.