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

Commit id: fd4bd3a530cf0262cb8055ab79cda07819cf006b

deletions | additions      

       

T(p, k) = \sum_{i=1}^{k}{\left[\floor{\log_2{p^{i-1}}} \cdot \floor{\log_2{p}} \right]}  \]  Since multiplication is the elementary operation, declarations, assignments and return statements are not counted.  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:  \begin{subequations}