Proving Algorithms

Question

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.

Answer 1

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.

Answer 2

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?