Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
What do you mean by "witnesses"? –  Arjang Oct 14 '12 at 22:41
1  
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. –  Max Morin 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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
Obviously they are simply the coefficients of the equations, which of course makes them obvious. But is that a safe assumption for most equations? –  MZimmerman6 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)$. –  Brian M. Scott 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. –  MZimmerman6 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 –  MZimmerman6 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. –  Brian M. Scott 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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.