1
$\begingroup$

I am trying to figure out some stuff here with Big O Notation. I mean I understand the concept of it and can generally be able to tell what the efficiency of something is, but I do not really understand how to find witnesses. Here is an example of one that I need to do. Can anyone help me understand this? Thanks in advance!

Example 1: $n^2$ is $O(0.001n^3)$.

Example 2: $25n^4 − 19n^3 + 13n^2 − 106n + 77$ is $O(n^4)$.

  • 0
    Note that the $0.001$ in $O(0.001n^3)$ (or any other constant inside an $O$-term) is meaningless, as $O(0.001n^3) = O(n^3)$.2012-10-14

2 Answers 2

1

HINTS: For (1), try $c=1000$. For (2), try $c=25+19+13+106+77$. In each case think about why I suggested those particular numbers. (Note that they’re not the only ones that work; anything bigger works just as well, for instance. But they are the most obvious ones to try.)

  • 0
    @MZimmerman6: You’re welcome! And yes, in simple cases there’s often an easy choice of $c$ and $k$ that makes one of them $1$.2012-10-14
0

I'm not sure what it means to find witnesses, but nevertheless:

  1. $n^2 = o(n^3)$, as well as $O(n^3)$ since $\lim_{n \to \infty}\frac{n^2}{0.001 n^3}=0$.

2.Do the same with the second expression: $\lim_{n \to \infty} \frac{a n^4 +b n^3 + c n+d}{s n^4} = \frac{a}{s}+o(1)=O(1)$ where $a,b,c,d,s$ are some constants.

  • 0
    corrected accordingly2012-10-14