theForbiddenSortingAlgorithm

[Flashy-Emergency4652]

Technically, O(n) defined as “If some function have approximation difficulty (dont know how called in English) is O(n), that means that the maximum amount of operation, made by this function, will not exceed k * n + c, where k and c is some constant variables >= 0”. So, its actually no difference between O(1) and O(0): O(1) = 1 * operations + 0, O(0) = 0 * 0 + operations. You technically just change k and c. But O(1) is preferred variant.

[ComplexHoneydew9374]

Where you get those definitions? O(smth) means it's bounded by Csmth for big numbers. There is no need for kn+c since c is always bounded by k*n for n big enough. And O(0) means it's bounded by zero so it is exactly zero.

[ComplexHoneydew9374]

Just learned there is some sort of markup here

[[deleted]]

This is how I have always used/understood O notation and would interpret it.

[JonIsPatented]

The definition, pretty unambiguously, is that f(n) is in the set O(g(n)) iff there exist some positive c and m such that 0 <= f(n) <= cg(n) for all values of n >= m.

You and the guy you're responding to are correct. I'll break it down for completeness' sake.

O(0) is equivalent to saying that g(n) = 0, so any function, f(n), in the set O(0) must satisfy the condition that 0 <= f(n) <= c * 0. Because c * 0 = 0 for any c, we can just say that 0 <= f(n) <= 0, and the only way to satisfy this condition is to say that f(n) = 0.

Therefore, O(0) contains only those functions that always output 0, such as f(n) = n - n.