this is for holding javascript data
Jeremy Ting edited p3.tex
about 10 years ago
Commit id: 7cdd26cfb56b41083ba403caa572e311cf46e829
deletions | additions
diff --git a/p3.tex b/p3.tex
index a8b1ae0..2ea52ff 100644
--- a/p3.tex
+++ b/p3.tex
...
$1 - N{1-m} = m^{h+1}$
$lg_{m}(Nm - N + 1) -1 = h$
So looking at large values of N and M, this formula is basically
$lg_{m}(Nm) = h$ because $Nm$ is the dominating term. So if $m^'=m^2$, then the height of $m^' is double M$.
$lg(Nm) = h$
$lg(N(m^')^2 = h$
$2lg(N) = h$
$lg(N) = \frac{h}{2}$
\item
Using Master Thoerem, we will be able to write the recursive cost of this function as:
\[T(n) = a +
(n/b) (\frac{n}{b}) + O(n^a)\]
The branching factor $a$ is 1 because we are only left with one subproblem at each iteration. Also doing $\frac{y}{2}$ takes constant time because $y$ is in the order of $2^n$, so dividing by 2 is just a simple bitshift. The subproblem is $n/2$ because you only have to deal with a number with half the bitsize. THe cost of combining the subproblems back to the larger problem is the cost of squaring a number and then take mod on a number order $2^0$.