The functions that are most commonly used for comparing algorithm efficiencies are power functions, such as n1/2,n,n2, and n3, and combinations involving a power function and an exponential or logarithmic function, such as 2n,log(n),nlog(n), and n2log(n)
For any positive rational numbers r and s and any integer n≥1,
if r≤s, then nr≤ns
1≤n≤n2≤n3.
Show that n4−5n−8 is O(n4)
Observe for every integer n≥1,
n4−5n−8≤n4+5n+8≤n4+5n4+8n4=14n4because whenn≥1,5n+8is positiveby transitivity of order theorem, sincen≥1thenn≤n4and1≤n4and so5n≤5n4and8≤8n4
Thus by transitivity of order and equality,
n4−5n−8≤14n4 for every integer n≥1
By definition of O-notation, n4−5n−8 is O(n4)