New answers tagged runtime-analysis
0
You say you have a number of 6 Megabits, that is $n < 2^{6,000,000}$.
We want to find numbers $b^k$ where b and k are integers, $2 ≤ b < 2^{31}$, k as large as possible such that $b^k ≤ n$, we you want to find the pair b, k that makes $n-b^k$ as small as possible. Since n is fixed, this is equivalent to making $n / b^k$ as small as possible, or ...
2
The value of $i$ at the $k$'th iteration (starting from zero) is $i_k := 2^k$. The inner loop runs $i_k$ times, for a total of $i_0 + i_1 + \cdots + i_K$, where $K$ is the largest number such that $i_K \leq n$, that is $\lfloor \log_2 n \rfloor$. Therefore the running time is
$$
\sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^k = 2^{\lfloor \log_2 n \rfloor + 1} - 1 ...
0
Number of CPU cycles
When evaluating the speed of (cryptographic) procedures its common to refer to the absolute number of cycles of the CPU
E.g. BIKE Cipher Specification (see page 30).
In terms of complexity all procedures are supposed to be polynomial in the input length. Additionally, the input lengths vary a lot, so any asymptotic notion would be ...
1
Yes, and AFAIR you can find it even in classic Knuth book. It's the number of operations performed, usually split by operation type. For example, number-crunching algorithms are measured in terms of FP adds and multiplications performed. Sorting algorithms are measured in terms of comparisons and swaps, and so on.
1
I think the comparison is a bit clouded actually. Some unspoken concerns are that you can't claim python will compile to precisely 72+8n bytes by reading the high-level code. There's a virtual machine with untold optimization and overhead heavily dependent on memory layouts, CPUs, your OS, even your version of Python. Memory blocks might be allocated in ...
Top 50 recent answers are included
