Very perplexed with this one. I have three implementations of an algorithm to calculate the factorial of a number. I calculated the average runtimes of each for input size up to 2500 and plotted them. From the visual inspection it seems that they don't exhibit linear time complexity but rather quadratic. To explore this further, I used curve fitting and the results emerging from visual inspection are confirmed.

Why is this happening? Is it maybe related to the way multiplication is handled in Python for small number? (see here Complexity of recursive factorial program)

import matplotlib.pyplot as plt
import numpy as np
import random
from scipy.optimize import curve_fit
import statistics as st
import timeit
import sys

sys.setrecursionlimit(3000)

def factorial_iterative(n):
    ''' Function that calculates the factorial of its argument using iteration
    
    Assumes that its argument is a positive integer
    Uses iteration
    Returns the factorial of the argument
    '''
    factorial = n
    while n > 1:
        n -= 1
        factorial *= n
    return factorial

def factorial_recursive_non_tail(n):
    ''' Function that calculates the factorial of its argument using non-tail recursion
    
    Assumes that its argument is a positive integer
    Uses non-tail recursion
    Returns the factorial of the argument
    '''
    if n == 1:
        return 1
    else:
        return n * factorial_recursive_non_tail(n - 1) 

def factorial_recursive_tail(n, factorial):
    ''' Function that calculates the factorial of its argument using tail recursion
    
    Assumes that its first argument is a positive integer
    Assumes that its second argument is an accumulator with a value of 1
    Uses tail recursion
    Returns the factorial of the argument
    '''
    if n == 1:
        return factorial
    else:
        return factorial_recursive_tail(n-1, n*factorial)

# max input size
n = 2500

# create input values list and initialise lists to store runtimes
n_values = list(range(1, n 1))
fact_iterative_runtimes_list = []
fact_non_tail_runtimes_list = []
fact_tail_runtimes_list = []

# for each n, time the implementation 100 times, calculate avg runtime, and store in dedicated list
for i in n_values:
    # iterative
    fact_iter_runtime = timeit.repeat(lambda: factorial_iterative(i), number=1, repeat=100)
    fact_iterative_runtimes_list.append(st.mean(fact_iter_runtime))

    # non-tail recursive
    fact_recursive_non_tail_runtime = timeit.repeat(lambda: factorial_recursive_non_tail(i), number=1, repeat=100)
    fact_non_tail_runtimes_list.append(st.mean(fact_recursive_non_tail_runtime))

    # tail recursive
    fact_recursive_tail_runtime = timeit.repeat(lambda: factorial_recursive_tail(i, 1), number=1, repeat=100)
    fact_tail_runtimes_list.append(st.mean(fact_recursive_tail_runtime))

# Plot avg runtimes against input sizes
plt.figure(figsize=(18, 6))
plt.plot(n_values, fact_iterative_runtimes_list, label = "Iterative")
plt.plot(n_values, fact_non_tail_runtimes_list, label = "Recursive non-tail")
plt.plot(n_values, fact_tail_runtimes_list, label = "Recursive tail")
plt.ylabel("Running time (seconds)")
plt.xlabel("Values of n")
plt.legend()
plt.show()

CodePudding user response：

As @Konrad has pointed out, it is due to the way multiplication is handled in Python.

For smaller numbers, simple school level multiplication (which runs in O(N^2)) is used. However, for bigger numbers, it uses the Karatsuba Algorithm, which has a estimated complexity of O(N^1.58) (N = length of the number). Since the multiplication isn't achieved in O(1), your time complexity isn't linear.

There are "faster" multiplication algorithms (such as Toom-Cook and Schönhage-Strassen) if you want to look into it.

CodePudding user response：

The complexity is linear in the number of multiplication if you assume that the multiplications are executed in O(1), but for large number that is not the case. Sorry for the vague explanation but the key point is that a multiplication between two number does take different time depending of the size of the input numbers.