What will be Big-O complexity for a recursive function whose number of calculations oscillate with n?

user_7475429 0
Viewed 1072

I have a function that finds the exponent but I am confused about the complexity of the function.

Function:

def expo(number, exponent):
    if exponent == 0:
        return 1
    elif exponent % 2 == 0:
        val = expo(number, exponent / 2)
        return  val * val
    else:
        return number * expo(number, exponent - 1)

I tried to calculate and draw a graph of the number of calculations according to the exponent and got this result: Graph: X-Axis exponent, Y-Axis respective calculations required Exponent : Calculations:

1 : 2, 2 : 3, 3 : 4, 4 : 4, 5 : 5, 6 : 5, 7 : 6, 8 : 5, 9 : 6, 10 : 6, 11 : 7, 12 : 6, 13 : 7, 14 : 7, 15 : 8, 16 : 6, 17 : 7, 18 : 7, 19 : 8, 20 : 7, 21 : 8, 22 : 8, 23 : 9, 24 : 7, 25 : 8, 26 : 8, 27 : 9, 28 : 8, 29 : 9, 30 : 9

As you can see the number of calculations is oscillating, I think Big-O notation will not be linear or quadratic. I think it will be like a multiple degree polynomial with representation like

enter image description here

Am I right or I just have the wrong idea of O(n) notation?

big-o complexity-theory algorithm python
2 Answers

This is a well known algorithm called fast exponentiation (sometimes square-and-multiply) and its complexity is O(log(n)). Wikipedia has a whole page on it: https://en.wikipedia.org/wiki/Exponentiation_by_squaring

But in case you didn't know these informations, one way of thinking it is to rewrite your algorithm so you can easily find the recurrence formula. The main difficulty is the different procedure applied to odd and even numbers. The trick is to group them together and make one recursive call only.

def expo(number, exponent):
    if exponent == 0:
        return 1
    elif exponent % 2 == 0:
        val = expo(number, exponent / 2)
        return  val * val
    else:
        return number * expo(number, exponent - 1)  # exponent - 1 is even !

can be rewritten

def expo(number, exponent):
    if exponent == 0:
        return 1
    elif exponent % 2 == 0:
        val = expo(number, exponent / 2)
        return  val * val
    else:
        return number * expo(number, (exponent - 1) / 2) ** 2

Now you can see that at each step of the algorithm, exponent is (roughly) divided by 2 (this does not depend on its parity anymore), thus the complexity is log(n).

user_81180870

First, you can consider the algorithm with the worst case. Hence, if T(n) is the time of the algorithm, the worst-case scenario is T(n) = T(n-1) + c (c is a constant number for the comparison, sum, calling a function, ...). Therefore, T(n) = O(n).

Also, the statement I think O(n) will not be linear or quadratic is not meaningful. If a function is in O(n), it means it is at most linear. Hence, it could not be quadratic.

Now you can scrutinize more into the time complexity computation and try to find a tight bound for the complexity. As, at least one time of two consecutive recursions, we will get an even value for exponent (as we have -1, if exponent is odd), Hence, the exponent reaches to 1, with at most 2 log(n) of computation (as the exponent will be divided by 2 at least in each 2 consecutive recursion). Therefore, a tight bound for T(n) is O(log(n)).

user_37688710
Related