Mazdak Farrokhzad edited b) Algorithm.tex  almost 10 years ago

Commit id: 9a20cd71ab4d6af31097165c8907bb5a2f453478

deletions | additions      

       

For this algorithm, if we use the input itself to calculate the running time, we get:  \[  T(p, k) = \sum_{i=1}^{k}{\left[\floor{\log_2(p^{i-1})} \sum_{i=1}^{k}{\left[\floor{\log_2{p^{i-1}}}  \cdot \floor{\log_2(p)} \floor{\log_2{p}}  \right]} \]  However, if we only know the length of the input, and not the numbers themselves, we get differing upper and lower bounds. A binary number of length $n$ is any number $k$ such that $\floor{\log_2(k)}=n$. The smallest such number is $2^n$, and the largest such number is $2^{n+1}-1$. Let $n=\floor{\log_2(k)}$ be the length of $k$, and $m=\floor{\log_2(p)}$ be the length of $p$. We then get: