3 ms·
Do you mean O(n^2)? Because merge sort certainly won't be exponential.
by Jtsummers 11y ago
Do you mean O(n^2)? Because merge sort certainly won't be exponential.
- Lxr 11y agoNo, I mean O(2^n). O(2^n) includes everything that grows slower than 2^n as well. It is no relation to the worst case performance of merge sort, just a clarification on the definition of Big O.
- deleted 11y ago[deleted]
- Jtsummers 11y ago> Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm. From higher up in the article. You picked the O(N) section description to pick a nit with the whole article when it covers exactly what you want it to earlier.
- nemetroid 11y agoThat's not what the grandparent is getting at. Big O describes an upper bound (and often, but not necessarily, refers to the worst-case scenario).