Difficulty figuring out the time complexity of this recursive function

Question

I think it's interesting but I'm not sure about my solution. This algorithm calculates xⁿ

If I use the master theorem my reasoning goes like this

T(n) = 2 T(n/2) + f(n)

But f(n) in this case is 1? Because n <= 4 is constant. Gives me:

T(n) = Θ(n)

If I use substitution I get this answer

T(n) = Θ(n + log(n))

I think I'm doing lots of things wrong. Can someone point me in the right direction?

Answer 1

T(n) = Θ(n + log(n)) is just T(n) = Θ(n). The lower order term (log(n)) can be omitted when using theta.

Also, f(n) is O(1) because you are only doing one multiplication (rek(x, n/2) * rek(x, (n + 1)/2)) for each recursion.

Answer 2

The complexity is 0(n). Explanation: You make there ALL multiplication as in using simple cycle. And you have no operation thats numbers divided by numbers of * are bigger than a const. So, complexity is about const*0(n) that makes 0(n).