Big O Notation and finding witnesses

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)$.

• What do you mean by "witnesses"? Oct 14 '12 at 22:41
• The definition you're using probably want you to find a pair $(N, c)$ s.t. for example $n^2<c\cdot 0.001 n^3$ for all $n>N$. If you manage to guess a reasonable constant you can probably find an $N$ for it really easily here. Oct 14 '12 at 22:43
• 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)$.
– TMM
Oct 14 '12 at 23:07

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.)

• Obviously they are simply the coefficients of the equations, which of course makes them obvious. But is that a safe assumption for most equations? Oct 14 '12 at 23:19
• @MZimmerman6: The absolute values of the coefficients, actually. For polynomials, yes: that’s how you prove the general theorem that if $p(x)$ is a polynomial of degree $n$, then $p(x)$ is $O(x^n)$. Oct 14 '12 at 23:21
• Okay, I understand that point then, but I guess I am just unsure what a "witness" tells me. It does not seem to give me valuable information. Oct 14 '12 at 23:25
• And also it is asking about a value of k for the witness as well. So what is the other term, I know c but what is k Oct 14 '12 at 23:27
• @MZimmerman6: The fact that you can produce witnesses at all gives you valuable information: it tells you something about the rate of growth of your function. That is, if you can produce witnesses $c$ and $N$ such that $|f(n)|\le c|g(n)|$ for all $n\ge N$, you’ve shown that $f$ is $O(g)$; and if $g$ is a nice, well-behaved function, especially one that doesn’t grow too fast, this tells you that $f$ behaves reasonably well too, at least in terms of rate of growth. Oct 14 '12 at 23:28

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.

• $n^2$ is both $O(n^3)$ and $o(n^3)$. In fact, if $f\in o(g)$, then $f\in O(g)$. Oct 14 '12 at 23:26
• corrected accordingly
– Alex
Oct 14 '12 at 23:30