CODEWITHSUNDEEP
pythonmathtime-complexity
Zaruya
Zaruya

Reputation: 81

Reducing the time the program takes to calculate large inputs

The below code calculates the sum of the result (x*k -y) n amount of times, with the value k starting at 1, and is incremented by 1 each time the loop runs:

def invoke(n,x,y):
    k=1
    sum1=0
    while(n > 0):
        result=x*k-y 
        k+=1
        sum1+= result
        n-=1 
    return sum1

For instance, calling the function with the values, invoke(2,3,5) would output -1 because for k=1, it is 3*1-5 = -2, and for k=2, it becomes 3*2-5=1. Hence, the program returns -1 as both -2 and 1 are added.

The problem, I am having is that it takes a while to calculate large numbers, is there any way to optimize this?

In an attempt to make it run faster, I wrote a recursive implementation of this program:

def invoke1(n,x,y):
     k=0
     if n == 0:
         return 0
     else:
         return x*(k+n)-y + invoke1(n-1,x,y)

However, this implementation is not much better as I get an error when calculating large numbers.

Upvotes: 1

Views: 126

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476574

Instead of looking for a way to do the same work faster, you should ask whether you have to do all the work in the first place.

Basically you want to compute:

 n
---
\
/     x * k - y
---
k=1

With x and y fixed. If we perform mathematical analysis on it, we know that this is equivalent to:

n * (n+1) * x
-------------  - n * y
      2

So we can calculate it as:

def invoke(n, x, y):
    return n * (n+1) * x / 2 - n * y

Or if we only perform calculations in the integer domain:

def invoke_ints(n, x, y):
    return n * (n+1) * x // 2 - n * y

Given the calculations are done in constant time (if the numbers are very huge, actually calculates are typically done in O(log n)), the time complexity is constant, if not, these are in O(log n).

The iterative and recursive function both work in O(n) (if the computations are in constant time), or O(n log n) in case the numbers are that huge that we do the calculations with arbitrary bit length. Recursion will usually slow down the process, since function calls in Python are quite expensive, and Python does not implement tail call optimization (TCO).

Upvotes: 6

Related Questions