Determining the order of a function with big Oh

Aug 2009
37
0
I was wondering if anyone could double check my answers below please.

Give the order of the following functions,

\(\displaystyle 1. Ta(n) = 20^2 + (n + 4)^3\)
\(\displaystyle 2. Tb(n) = (6n + 4)^2 + 3nlog2(n)\)
\(\displaystyle 3. Tc(n) = (7n + 1)^2log10(n)\)

I got the following orders:-

\(\displaystyle 1. \theta(n^2)\)
\(\displaystyle 2. \theta(n log n)\)
\(\displaystyle 3. \theta(log n)\)

Item 3 is the most effecient for very large values of n.
 
Feb 2010
100
27
Lebanon - Beirut
1) the expression of the third order since it contains \(\displaystyle n^3\) which dominates the whole expression, hence you get \(\displaystyle \theta(n^3)\)
2) you have a part which is of the second order: \(\displaystyle n^2\) and another one of order \(\displaystyle nlog_{2}(n)\) which is lower than \(\displaystyle n^2\) hence the total order is \(\displaystyle \theta(n^2)\)
3) Here, you have multiplication of a polynomial of the second order with \(\displaystyle log_{10}(n)\) hence the order is \(\displaystyle \theta(n^2log_{10}(n))\)

Clearly, the most efficient is the second one since \(\displaystyle n^2 < n^2log_{10}(n) < n^3\)