CODEWITHSUNDEEP
algorithmtime-complexitynumber-theory
user5205124
user5205124

Reputation:

How to determine the time complexity of this algorithm?

The following function calculates a^b. assume that we already have a prime_list which contain all needed primes and is sorted from small to large. The code is written in python.

def power(a,b):
    if b == 0:
        return 1

    prime_range = int(sqrt(b)) + 1
    for prime in prime_list:
        if prime > prime_range:
            break
        if b % prime == 0:
            return power(power(a, prime), b/prime)

    return a * power(a, b-1)

How to determine its time complexity? p.s. The code isn't perfect but as you can see the idea is using primes to reduce the number of times of arithmetic operations. I am still looking for an ideal implementation so please help if you come up with something. Thx!

Upvotes: 2

Views: 245

Answers (1)

Luka Rahne
Luka Rahne

Reputation: 10507

Worst case when for loop is exausted. But in this case b becomes divided by 2 in next recursive call.

In worst case we devide b by factor 2 in approx sqrt(b) operations in each step until b reach 1.
so if we set equations

f(1) = 1 and f(n) = f(n/2) + sqrt(n)

we get using woflram alpha

f(n) = (1+sqrt(2)) (sqrt(2) sqrt(n)-1)
and that is
O(sqrt(b))

Upvotes: 1

Related Questions