Measuring complexity for powering a number

I implemented a program for powering a number (a^n) using the divide and conquer technique. i implemented two versions of the same problem:

Version 1:

def input_params():
    a=input('Input \'a\' & \'n\' for a^n:')
    n=input('')
    result=power(a,n)
    print (result)

def power(a,n):
    if n<=1:
        return a

    elif n%2==0:
        return pow(power(a,n/2),2)

    else:
        return pow(power(a,(n-1)/2),2)*a

  if __name__ == "__main__":
    input_params()

Version 2:

def input_params():
    a=input('Input \'a\' & \'n\' for a^n:')
    n=input('')
    result=power(a,n)
    print (result)

def power(a,n):
    if n<=1:
        return a

    elif n%2==0:
        return power(a,n/2)*power(a,n/2)

    else:
        return power(a,(n-1)/2)*power(a,(n-1)/2)*a



if __name__ == "__main__":
    input_params()

Version 3:

def input_params():
    a=input('Input \'a\' & \'n\' for a^n:')
    n=input('')
    result=power(a,n)
    print (result)

def power(a,n):
    if n<=1:
        return a

    elif n%2==0:
        return square(power(a,n/2))

    else:
        return square(power(a,(n-1)/2))*a

def square(num):
    return num*num

if __name__ == "__main__":
    input_params()

Q1: Which one of the above versions have a complexity of θ(lg n)?

Q2: If version 2 has the co开发者_开发问答mplexity of θ(lg n), why? Because although the problem size in Version 2 is being divided by two, the number of sub problems are also two, so I feel Version 2 will grow in the order of θ(nlg n) .

I am not sure about my conclusion.

Thanks

In version 1, there's no answer as you use a function called pow which you never define, so one can't really say what the complexity is.

In version 2, there are redundant calculations, so the answer depends on whether you consider those redundant calculations as being part of your complexity or not (as they can easily be left out).

Try writing version 3 in terms of a function called square and include a definition for square

In all cases you need some assumptions about the cost of the basic operations (*, /, and +) you use. You probably want to assume they all cost O(1), but you should make that clear in your analysis.