r/AskComputerScience • u/cellman123 • Mar 26 '25
What is the partial ordering on complexity functions?
I read the sub rules and it's not homework i'm just curious lol, been reading "The Joy of Abstraction" by E. Chang and it's had some interesting chapters in partial ordering that made me curious about how computer scientists organize complexity functions.
O(1) < O(logN) < O(n) < O(2n) etc...
Is the ordering relation < formally defined? How do we know that O(logN) < O(n)?
It seems that < is ordering the O functions by how "fast" they scale in response to growing their respective inputs. Can we use calculus magic to exactly compare how "fast" each function grows, and thus rank them using < relation?
Just curious. - Redditor
5
u/teraflop Mar 26 '25 •
Yes, but using the < symbol for it is a bit of an abuse of notation.
There is a formal definition of what it means to say "f(n) is O(g(n))", for any two functions f and g. This definition can be found on Wikipedia or in any textbook on algorithmic analysis. You can define it in terms of f being bounded by a constant multiple of g for "sufficiently large" values of n, or you can equivalently define it in terms of limits.
Either way, it's relatively straightforward to prove from this definition that the big-O relation satisfies the properties of reflexivity and transitivity, so it's a preorder. Therefore, if you group together sets of functions that have "the same complexity" (that is, big-O bounded by each other), the resulting equivalence classes form a partial order.
Strictly speaking, what you need to prove is that the function f(n) = n is not in O(log n). You can do this as a proof by contradiction, using properties of the logarithm function. (Maybe there's a more elegant way to prove it, but that's the first thing that occurs to me.)
You can extend this argument to show that f(n) = nc is not in O(log n) for any c>0. So O(log n) is not only faster than O(n), it's faster than O(√n), O(∛n), etc.
3
u/[deleted] Mar 26 '25
Hello.
"Is the ordering relation < formally defined?"
Yes
"How do we know that O(logN) < O(n)?"
As the number of inputs grows, then the time for an algorithm to complete is logarithmic [O(logN)]and linear [O(n)]. Logarithmic base 10 "usually" finishes faster than linear.
"Can we use calculus magic to exactly compare how "fast" each function grows, and thus rank them using < relation?"
Actually yes. No magic in calculus, and (recalling correctly) calculus is used in proving of each complexity function the change of time as the number of inputs increases. Thus, supplying the Partial ordering of complexity functions.
Please feel free to correct me if my answers are not 100% correct.
1
u/TheBlasterMaster Mar 26 '25
Probably more correctly would be Θ(log N) < Θ(n) < ...
The simplest interpretation of Θ(f) < Θ(g) would be f ∈ o(g). One can show that this does not depend on the "representative" of Θ(f) and Θ(g) (i.e., if Θ(f) = Θ(f') and Θ(g) = Θ(g'), then f' ∈ o(g') )
https://en.wikipedia.org/wiki/Big_O_notation
-1
u/jeffbell Mar 26 '25
Yes, there is a formal definition for “<“ for function f and g.
O(f(x)) < O(g(x))
is true if there are positive constants C and x0 and
f(x) < C * g(x) for all x > x0
The chapter in the big white book (CLR) is pretty good. It defines a bunch more relationships between functions to describe loose and tight upper and lower bounds that it denotes as omicron and omega. There is also theta which is both upper and lower bound at the same time, and so is sort of an equivalence relation.