1
$\begingroup$

I am doing some old multiple choice tests in order to prepare for an exam. However, I am stuck between solving the magnitudes questions some nice links would be appreciated as well as an answer.

The question: Which of the functions has magnitude equal to $n^2+n^3log(n)$?

1) $n^2+log(n)$
2) $n^3log(n^2)+n$
3) $n^4log(n)$
4) $n^3+n^2log(n)$
5) $n^3(log(n))^2$
6) $2^n+n^3log(n)$

I am sure that its not 1) 3) 5) 6).
As their exponents aren't 6 as is the first?. However I am kinda stuck whether to choose 2 and 4. I know the right answer is supposed to be 2).

1 Answers 1

1

Note that for sums, you can ignore the smaller term. Your test function is then $n^3 \log(n)$. Item 4 is $n^3$. For item 2, you can use the laws of exponents to say it is $n^3 \log (n^2)=2 n^3 \log (n)$

  • 1
    Further to this, if you don't know 'big O' notation then a summary can be found here. https://en.wikipedia.org/wiki/Big_O_notation Usually functions are considered equal in magnitude if one is eventually less than a constant multiple of the other. We say that $f(x) = \mathcal{O}g(x)$ in that case.2012-10-30
  • 0
    Thanks man. Actually I could erase all of the others after ignoring all the small terms, than 2 :)2012-10-30
  • 1
    Yes, the question is essentially asking which function has dominant term in common with this one. Don't forget to accept the answer! (The tick thing)2012-10-30