5

I am confused how to do this question. Intuitively it doesn't even make sense how a function $f$ plus another function is in $O(f)$. How can I approach this question: $$ n\log(n^7)+n^{\frac{7}{2}} \in O(n^{\frac{7}{2}}). $$

We know the fact that $\log n < n$ and I tried factoring out the $n$ but I am stuck. Any hints would be appreciated, Thanks!

Alex M.
  • 35,207
Amir Mousavi
  • 171
  • 2
    Use the definition of big $O$. You need to show that $7n\log(n)\le C\cdot n^{7/2}$ for all $n\ge n_0$. – Dietrich Burde Mar 25 '16 at 19:21
  • 2
    Intuitively, since $n\log(n^7) = 7n\log(n) \sim n\log(n) < n^2 < n^{7/2}$, the term $n^{7/2}$ dominates the expression. – Mike Pierce Mar 25 '16 at 19:21
  • 1
    What Mike said. Big O is all about which function dominates, and in this case the $n^{7/2}$ massively dominates the $n\log n$. To build intuition, try similar exercises with simpler functions, e.g., show $n^2 + n \in O(n^2)$, and think about what kind of contribution $n$ makes to $n^2+n$ when $n$ is extremely large. –  Mar 25 '16 at 19:24
  • But there is also a $$n^{\frac{7}{2}}$$ which I can't add to the equality. Right now I have $$7nlog(n) <= 7n^2 <= 7n^{\frac{7}{2}}$$ – Amir Mousavi Mar 25 '16 at 19:36
  • Now that you have $7 n \log n\leq 7 n^{7/2}$ then $(7 n\log n)+7 n^{7/2}$ $\leq 2\cdot 7 n^{7/2}=O(n^{7/2}).$ Because from the def'n, we always have $2 f(n)=O(f(n)).$ – DanielWainfleet Mar 25 '16 at 20:23

2 Answers2

4

The easiest way is to take the limit: $\frac{n^{\frac{7}{2}}+7 n \log n}{n^{\frac{7}{2}}} \to_n 1$, hence these two functions are of the same order.

Alex
  • 19,262
2

Actually, this shouldn't be too terribly surprising. Indeed, if $g \in O(f)$, then it is always true that $f + g \in O(f)$. To see this, note that since $g \in O(f)$, there exists $n_0, C > 0$ such that for all $n > n_0$, $g(n) \leq Cf(n)$, by definition. Therefore, for all $n > n_0$, $(f+g)(n) = f(n) + g(n) \leq (C+1)f(n)$, which shows that $f + g \in O(f)$,

Intuitively, this makes sense. If $g$ does not grow faster than $f$ asymptotically, then $f + g$ shouldn't grow any faster than $2f$ asymptotically. But that is a constant multiple of $f$, so it has the same asymptotic order. Note that $C = 2$ isn't the correct constant to use, since $g$ may already be larger than $f$ by some constant, but the idea is the key. You may add any finite number of functions that are $O(f)$ to $f$ without making its asymptotic growth any larger.

For your particular problem, write $n\log(n^7) = 7n\log(n)$ and then note that $7n\log(n) \leq 7n^2 \leq 7n^{7/2}$ using the fact that $\log(n) < n$. Therefore, for all $n > 0$,

$$ n\log(n^7) + n^{7/2} \leq 7n^{7/2} + n^{7/2} = 8n^{7/2}, $$

which shows that $n\log(n^7) + n^{7/2} \in O(n^{7/2}).$

Jeremy West
  • 275