algorithmscomputer sciencediscrete mathematicslogic
I'm very stumped on this problem I have and was wondering if anyone could lend me a hand here?
Suppose that you have two different algorithms for solving a problem. To solve a problem of size $n$, the first algorithm uses exactly $(n^2)(2^n)$ operations and the second algorithm uses exactly $n!$ operations. As $n$ grows, which algorithm uses fewer operations?
The multiply by $2$ is no different than in elementary school when you're taught how to divide by $10$, $100$, $1000$, etc. by moving the decimal place. Let me do this backwards as an example. Say you are told that the wavelength of green light is $0.000\ 000\ 510$ meters--how many nanometers is this? The conversion is $0.000000510 \text{ meters } * \frac{10^9 \text{ nm}}{1 \text{ meter}}$. So you just multiply by $10^9$ to get the nanometers. This can be done by moving the decimal nine places to the right: first move it three spots: $000.000510$, next move it three more places ($6$ total): $000000.510$, and finally move it three more (total of $9$): $000000510 = 510$ nm.
Converting Fractional Numbers
Finding decimal values for base two is essentially the same. Formally think about what you are trying to do. Let's find the base $2$ form of a value $x$ which we know is positive and less than $1$:
$$ x = n_1 \frac{1}{2} + n_2\frac{1}{2^2} + n_3\frac{1}{2^3} + \dots = \sum_1^\infty a_n \frac{1}{2^n} $$
Finding the base two representation amounts to finding all $a_n$ (most of which will be $0$ if the number is "nice"--which most aren't). If we multiply both sides by $2$ then what do we get?
$$ 2x = n_1 + n_2\frac{1}{2^1} + n_3\frac{1}{2^2} + \dots = a_1 + \sum_1^\infty a_{n+1}\frac{1}{2^n} $$
Since this is base $2$, $a_1$ must be either $0$ or $1$. Which one it is will be obvious once we multiply $x$ by $2$. For example if we want to find $x = 0.3125$:
$$ 2*0.3125 = 0.625 = a_1 + \sum_1^\infty a_{n+1}\frac{1}{2^n} $$
$a_1 = 0$ because there is no whole part--we still get a decimal so now we are trying to solve a different problem:
$$ 0.625 = \sum_1^\infty b_n\frac{1}{2^n} $$
This is the same as the original problem! Now we are trying to find the binary representation of $0.625$ (this will give the $b_n$'s). But we need to keep in mind that the $b_n$'s represent $a_{n+1}$ from the original problem! So we recurse:
$$ 2*0.625 = 1.25 = b_1 + \sum_1^\infty b_{n+1}\frac{1}{2^n} \rightarrow b_1 = a_2 = 1 \\ 0.25 = \sum_1^\infty b_{n+1}\frac{1}{2^n} = \sum_1^\infty c_{n}\frac{1}{2^n} \\ 2*0.25 = 0.5 = c_1 + \sum_1^\infty c_{n+1}\frac{1}{2^n} \rightarrow c_1 = b_2 = a_3 = 0 \\ 0.5 = \sum_1^\infty c_{n+1}\frac{1}{2^n} = \sum_1^\infty d_{n}\frac{1}{2^n} \\ 2*0.5 = 1 = d_1 + \sum_1^\infty d_{n+1}\frac{1}{2^n} \rightarrow d_1 = c_2 = b_3 = a_4 = 1 \\ 0 = \sum_1^\infty d_{n+1}\frac{1}{2^n} \rightarrow d_{n > 1} = c_{n > 2} = b_{n > 3} = a_{n > 4} = 0 $$
So this gives: $0.3125_{10} = 0.0101000\dots_{2}$ or just $0.0101_2$ (which indeed is $0.3125 = \frac{5}{16} = \frac{1}{4} + \frac{1}{16}$).
Converting Integers
Now let's look at converting integers to binary it's essentially the same thing except now you don't have powers of $\frac{1}{2}$, you have powers of $2$:
$$ x = a_0 + a_1*2 + a_2*2^2 + a_3*2^3 + \dots = \sum_0^\infty a_n*2^n = a_0 + \sum_1^\infty a_n*2^n = a_0 + 2*\sum_0^\infty a_{n + 1}*2^n $$
Hopefully that shows why we should divide by $2$. When we divide by $2$ what we are really doing is writing $x = 2\alpha + \beta$, plug that in:
$$ x = 2\alpha_0 + \beta_0 = a_0 + 2*\sum_0^\infty a_{n + 1}*2^n $$
Clearly $a_0 = \beta_0$ and $\alpha_0 = \sum_0^\infty a_{n + 1}*2^n$. So again, we recurse:
$$ \alpha_0 = 2\alpha_1 + \beta_1 = a_1 + 2\sum_0^\infty a_{n + 2}*2^n \rightarrow a_1 = \beta_1 \\ \alpha_1 = 2\alpha_2 + \beta_2 = a_2 + 2*\sum_0^\infty a_{n + 3}*2^n \rightarrow a_2 = \beta_2 \\ \dots $$
So, for instance, we can do $x = 45$:
$$ 45 = 2*22 + 1 \rightarrow a_0 = 1\\ 22 = 2*11 + 0 \rightarrow a_1 = 0\\ 11 = 2*5 + 1 \rightarrow a_2 = 1\\ 5 = 2*2 + 1 \rightarrow a_3 = 1\\ 2 = 2*1 + 0 \rightarrow a_4 = 0\\ 1 = 2*0 + 1 \rightarrow a_5 = 1\\ 0 = 2*0 + 0 \rightarrow a_6 = 0 \\ \dots \\ \text{it repeats--these are the zeros to the left of the integer} $$
So this gives $45_{10} = 0\dots000101101_2$ or just $101101_2$. The way we recursed suggests that we could write:
\begin{align} 45 = & 2*22 + 1 \\ =& 2*\left(2*11 + 0\right) + 1\\ =& 2*\left(2*\left(2*5 + 1\right) + 0\right) + 1\\ =& 2*\left(2*\left(2*\left(2*2 + 1\right) + 1\right) + 0\right) + 1 \\ =& 2*\left(2*\left(2*\left(2*\left(2*1 + 0\right) + 1\right) + 1\right) + 0\right) + 1 \\ =& 2*\left(2*\left(2*\left(2*\left(2*\left(2*0 + 1\right) + 0\right) + 1\right) + 1\right) + 0\right) + 1 \\ =& 2*\left(2*\left(2*\left(2*\left(2*\left(2*\left(2*0 + 0\right) + 1\right) + 0\right) + 1\right) + 1\right) + 0\right) + 1 \\ =& 2*\left(2*\left(2*\left(2*\left(2*\left(2*\left(2*\left(2*0 + 0\right) + 0\right) + 1\right) + 0\right) + 1\right) + 1\right) + 0\right) + 1 \\ =&\dots \end{align}
The reason that you divide to get the integer value and multiply to get the fractional value is because you are moving the digits towards the one's place: $2^0$. When the digits are to the left of the decimal (integers) you need to divide by $2$ to move them towards $2^0$ and when the digits are to the right of the decimal (fractions) then you need to multiply by $2$ to bring the digits closer to $2^0$.
Another example: base $3$
Let's say we want to find $45_{10}$ in base $3$. It's the same procedure--divide by $3$:
\begin{align} 45 =& 3*15 + 0 \\ =& 3*\left(3*5 + 0\right) + 0 \\ =& 3*\left(3*\left(3*1 + 2\right) + 0\right) + 0 \\ =& 3*\left(3*\left(3*\left(3*0 + 1\right) + 2\right) + 0\right) + 0 \\ =& 3*\left(3*\left(3*\left(3*\left(3*0 + 0\right) + 1\right) + 2\right) + 0\right) + 0 \\ \end{align}
So now that we are starting to get $0$'s, we know that $45_{10} = 0\dots001200_3 = 1200_3 = 1*3^3 + 2*3^2 = 27 + 18 = 45$
Best Answer
For $n\ge 3$ we have $n! \ge n^2 2^n$.
Indeed, let's try a proof by induction: $$ (n+1)! = (n+1)n! \ge (n+1) n^2 2^n $$ When do we have $(n+1) n^2 2^n \ge (n+1)^2 2^{n+1}$ so that we can complete the induction step?
This simplifies to $n^2 \ge 2(n+1)$, which holds iff $n\ge3$.