# Tag Info

## Hot answers tagged runtime-analysis

3

The most common approach is to take the longest number, and divide it in half (rounding an odd number of digits arbitrarily). So for x = 12345 y = 2478 you would get a=12, b=345, c=2, d=478. Since the number of digits in x is not even, we are free to choose whether to split into a=12 and b=345 or a=123 and b=45; it makes no difference to the running time. ...

2

I think in this case we should pad with zeros up to an even degree of the largest of the two numbers. Suppose that $x \ge y$ and $2^n \le x < 2^{n+1}$. Then one should represent $x, y$ as $$x = x_1\cdot 2^{\lceil \frac{n}{2} \rceil} + x_2, y = y_1\cdot 2^{\lceil \frac{n}{2} \rceil} + y_2$$ and then apply Karatsuba Rule. The total complexity is still $O(... 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 ...

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 ...

Only top voted, non community-wiki answers of a minimum length are eligible