0
$\begingroup$

I have the following algorithm:

def pow1(n):
    """Return 2 ** n, where n is a non-negative integer."""

    if n == 0:
        return 1

    x = pow1(n // 2)

    if n % 2 == 0:
        return x * x

    return 2 * x * x

In theory, using the Master Theorem, I've come to this conclusion:

The algorithm has one subproblem ($a = 1$), the subproblem size halves with each call ($b = 2$) and the work outside recursion is constant ($f(n) = 1$). (In reality it is some constant time depending on e.g. the implementation of division/module.) Looking at the expression $n^{\log_b a}$ and substituting we have that

$n^{\log_b a} = n^{\log_2 1} = n^0 = 1$

and since this is (roughly) equal to $f(n)$ the final runtime, according to the theorem, is

$\Theta(n^{\log_2 1} \log n) = \Theta(\log n)$

But when I run benchmarks on this with $n$ from $10$ up to $10^7$ I get a more or less linear increase in running time. So my questions are:

  1. Is there something I'm missing when applying the Master Theorem that would imply that the complexity even in fact linear?

  2. Is there something in the algorithm itself that is linear that I'm missing?

EDIT:

I realise now that the main point of confusion for me was mixing up what $n$ means. When discussing the time complexity of multiplication, $n$ usually signifies the size of the multiplied numbers, not the numbers themselves. For example, Python uses a multiplication algorithm for small numbers that has the time complexity $O(n^2)$, but that does not mean that if you make the numbers twice as large, the time increases by a factor 4. The increase in number of digits will determine the time complexity. Multiplying two $n$ digit numbers (in base 2) will produce a $2n$ digit number which should make it obvious that if we instead let $n$ signify the size of the number, the time complexity is $O(n)$.

$\endgroup$
11
  • $\begingroup$ The algorithm has linear complexity. That fact that it is calculating an exponential is different from the fact that as you increase $n$ the computation time increases approximately linearly. $\endgroup$ Apr 23 '20 at 18:04
  • 2
    $\begingroup$ Is multiplication $O(1)$ when you work with numbers up to $2^{10000000}$? $\endgroup$ Apr 23 '20 at 18:04
  • $\begingroup$ @DavidG.Stork We have $T(n)=T(n/2)+const$ (provided the basic operations such as multiplication are $O(1)$), so $O(\log n)$ is correct $\endgroup$ Apr 23 '20 at 18:08
  • $\begingroup$ @HagenvonEitzen: Yes, multiplication is ${\cal O}(1)$ because it is performed by using logarithms. $\endgroup$ Apr 23 '20 at 18:12
  • $\begingroup$ These are conflicting answers. One of you is saying it's linear, the other that it's logarithmic. :) Because Python uses the Karatsuba multiplication algorithm for large numbers, the complexity of that operation is $O(n^{1.585})$, does that somehow influence the total complexity? @DavidG.Stork Is it linear because the number of steps has a linear relationship to the number $n$? How would I make that formal analysis? $\endgroup$ Apr 23 '20 at 18:35
0
$\begingroup$

Since the result has $O(n)$ digits, merely the return value in memory takes $O(n)$ time. Indeed, the x * x step takes $O(\log x)=O(n)$ time. Therefore, you want the last term in the master algorithm to be $O(\log x)=O(n)$, not $O(\log n)$.

$\endgroup$
7
  • $\begingroup$ This is confusing to me. Isn't that mixing space complexity and time complexity? $\endgroup$ Apr 23 '20 at 18:29
  • $\begingroup$ @MarkusAmaltheaMagnuson I can understand you thinking that about the memory comment, but I'd disagree because editing memory still takes time. But the rest of the answer understands how long multiplication takes, so no, it's not mixing them up. This is the point Hagen von Eitzen made. BTW, their comments don't contradict David G. Stork's, because multiplication's logarithmic (in both space and time) in the numbers it multiplies, and linear in the $n$ parameter of your function. $\endgroup$
    – J.G.
    Apr 23 '20 at 18:36
  • $\begingroup$ @j-g Lots to unpack here, thank you for your comments. I think I need to go deeper with this, there's obviously something not clicking at the moment. $\endgroup$ Apr 23 '20 at 18:44
  • $\begingroup$ @MarkusAmaltheaMagnuson Time the multiplication of numbers with many digits. $\endgroup$
    – J.G.
    Apr 23 '20 at 18:48
  • $\begingroup$ @j-g I've timed multiplication and it seems like it happens in constant time, at least for factors with up to 400 digits. But that contradicts that the multiplication step is $O(n)$? $\endgroup$ Apr 23 '20 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.