0

I made a statement in my coursework that the term with the largest growth rate for an arbitrary function f(x) is always the most simple g(x) in Big O/Theta/Omega Notation (removing coefficients). I believe this to be true, but I'd like more confirmation that my own assumptions.

Definition of Big Theta Notation:

f(x) = Θ(g(x)) as x → ∞ ⇔
∃M1 > 0 ∃M2 > 0 ∃x0 > 0 such that ∀x ≥ x0, M1 ⋅ g(x) ⩽ f(n) ⩽ M2 ⋅ g(x)

Suppose that $f(x) = n^2 + n + 1$. In this case, the highest growth rate would be $n^2$ and $g(x) = n^2$.
Suppose that $f(x) = 2n + 1$. In this case, the highest growth rate would be $n$ and $g(x) = n$.
Suppose that $f(x) = n^5 + n^4$. In this case, the highest growth rate would be $n^5$ and $g(x) = n^5$.

Is the statement "the term with the largest growth rate for an arbitrary function f(x) is always the most simple g(x) in Big O/Theta/Omega Notation (removing coefficients)" true?

Alex Hira
  • 49
  • 1
    What do you mean by "most simple"? What if, say, $f(x) = 2^n e^{2 \pi i \alpha n} + n$ where $\alpha$ is irrational? – Qiaochu Yuan Oct 09 '20 at 18:28
  • By most simple, I meant the strongest best Big O statement that I could make with the function. Reading "Total n00b’s guide to Big O, Big Ω, & Big θ", he made a point where $n = O(n^2)$ is valid but not the strongest Big O Notation. In your example, I'd assume $2^n$ would be the best representation for Big O/Ω/θ because I think it has the highest growth rate out of all the terms? – Alex Hira Oct 09 '20 at 18:52
  • 1
    It depends on what you mean by "strongest" but yes, that's basically true. More precisely you need $f(x)$ to be a finite sum of functions (number of terms not depending on $x$) such that the term with the highest growth rate has the property that all the other terms are little-o of it. – Qiaochu Yuan Oct 09 '20 at 18:59

0 Answers0