3 ms·
This is completely wrong. Big O has nothing to do with algorithms. Big O notation can be used for any mathematical function from an ordered set to another order
by umanwizard 8y ago
This is completely wrong. Big O has nothing to do with algorithms. Big O notation can be used for any mathematical function from an ordered set to another ordered set, including average runtime of an algorithm as a function of data size, worst-case runtime of an algorithm as a function of data size, guaranteed amortized runtime of an algorithm as a function of data size, or anything else (including things with nothing to do with computation -- it's perfectly reasonable to say things like x^2 + 5x + 2 is O(x^2) and just be talking about pure math with no reference to algorithms).
If someone asked "what is the runtime of quicksort in big O terms", it is ambiguous whether the answer is O(n^2) or O(n*log(n)) , since it's not clear which function you're talking about.
- enedil 8y agoTo be honest, this is false too. You need functions with values that can be multiplied by scalars. If you just have ordered set, then you can't account for this constant from the definition. Alternatively, you could say that values of the function need to be from a normed vector space (but I'm not sure if it can be extended furthermore. Maybe normed C-module?)
- umanwizard 8y agoSure, but that doesn't change my point.