0
$\begingroup$

I'm trying to get down how to prove that something is $O(\cdots)$ or $\Theta(\cdots)$ but no matter what I look at, I don't get the reasoning as to how I can come to an answer.

So here's a couple of examples I've looked at:

  1. Show that for any real constants $a$ and $b$, where $b > 0$, $(n+a)^b = \Theta(n^b)$

  2. Show that $\log_2(n!) = O(n\log _2 (n))$

For 1 I understand that I have to show:

$$c_1 n^b \leq (n+a)^b \leq c_2 n^b$$

Do I just plug in random numbers until something works? That's what all the sites I've looked at seem to be doing, but that doesn't make sense.

For 2 I know that I have to show:

$$0 \leq \log_2(n!) \leq c(n\log_2(n))$$

Again, where do I even start? I can't wrap my head around any of this. :( Thanks for your help and patience.

$\endgroup$
  • $\begingroup$ HINT: If I recall correctly, for two functions $f,g$, $g$ being $O(f)$ means that $g$ asymptotically behaves like $f$. This means that for your first example, you are not showing that $$ c_1n^b \le (n+a)^b \le c_2n^b $$ for some constants $c_1,c_2$, but that for some number $N$, the previous bounds hold true when $n \ge N$. This should help you significantly. $\endgroup$ – skrub Sep 15 '14 at 23:24
1
$\begingroup$

Intuitively, the first is saying that as $n$ gets large, you don't care about adding or subtracting a constant to the base in $n^b$.

You don't plug in something random, you have to think about what you can prove. For the first, if you knew that $a$ is positive, you could use $c_1=1$ and argue that as $n \lt n+a, 1\cdot n^b \lt (n+a)^b$ This fails if $a \lt 0$, but decreasing $c_1$ a bit will make it OK with a bit more work. Remember that we are talking about asymptotic behavior when $n$ is large, so it doesn't have to be true for all $n$, just for $n$ large enough. So if we take $c_1=0.9^b$ and $a \ge 0$ we can say $0.9^bn^b \lt (n+a)^b$ If $a \lt 0,$ we require that $n \gt -10a$. Then $0.9^bn^b =(0.9n)^b \lt (n+a)^b$ and we have that side. For the left side, the challenging point is when $a \gt 0$. We take $c_2=2^b$ (anything greater than $1$ will work, with a change to the minimum $n$) and require that $n \gt a$ Then $(n+a)^b \lt (2n)^b = 2^nb^n$

For the second, the left side is obvious as $n! \ge 1$ To get the right side, you should argue from Stirling's approximation, which looks much like what you have.

$\endgroup$
0
$\begingroup$

It helps to draw a graph: to show that $f$ is $\Theta(g)$, you want to show that

(1) if you multiply $g$ by a large enough number, then its graph will be above the graph of $f$

(2) if you multiple $f$ by a large enough number it's graph will be above the graph of $g$, or equivalently, if you multiply g by a 8small enough* number, it's graph'll be below that of $f$.

Since the "numbers" you have to use depend on the functions $f$ and $g$, graphing is a great place to start. You say "Well, it looks as if twice $f$ is larger than $g$, so I'll pick $c_2 = 2$, or perhaps something larger to make the proof easier." So while one book might prove a theorem using $c_2 = 2,$ another might use $c_2 = 17$. You don't have to find the SMALLEST $c_2$ that works (which is nice, because doing that's a pain!).

What about your first probelm above? Well, that's a tough one, becasue it's realyl a whole class of problems all at once. I suggest you instead prove that $(n+2)^3 $ is $\Theta(n^3)$, and a few other similar things, adn then see whether you can generalize.

For the second, I'd suggest trying to find something simple that's a bit larger than $log(n!)$...something that's easy to simplify. How 'bout $\log(n^n)$? Since $n^n$ is $n$ copeis of $n$ multiplied togheter, adn $n!$ is $n$ numbers that are all no larger than $n$, that might work...

Does that get you anywhere?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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