def pow(x, n):
    print("pow " + str(x) + " " + str(n))
    # base case
    if n == 0:
        return 1
    if n < 0:
        return 1.0 / pow(x, -1 * n)
    if n % 2 == 1:
        return x * pow(x, n - 1)

    p = pow(x, n / 2)
    return p * p

This function is recursive.  First, how much does a single call cost, if we ignore the other recursive functions it might call (we'll charge them their own costs)?

Looks like it's just simple arthemetic computations.  So a single call to pow(x, n) takes a constant time, call it c.
When pow(x, n) is called, how many recursive calls are made in total?  It's useful to draw the recursion tree and see how deep it is in a few cases.

Let's look at a simple case, where n is a power of 2.  For example, imagine n is 64.  Since n is even, we end up in the case that executes line 11.  Since n is a power of 2, after dividing in half, we still have an even number.  It will be the same case again for the next recursive call, and the following, almost all the way down the the base case.  pow(x, 64) will call pow(x, 32) will call pow(x, 16) will call pow(x, 8) will call pow(x, 4) will call pow(x, 2), will call pow(x, 1), will call pow(x, 0).

That's lg(n) calls, plus a few at the end.  So if n is a power of 2, it's Theta(log n).  That's actually the best case.

What's the worst case for n?  If n is odd, then we don't divide n by two, but only subtract.  So the recursion tree could be deeper.

But notice that if you have an odd number, then you will subtract one, and get an even.  Then divide by two.  So even in the worst case, every other recursive call will divide the current n by two.  This means that there will be at most 2 lg(n) calls (plus a few at the end for the 1 and 0 cases).  That's still Theta(log(n)).

Since the result is Theta(log(n)) in the best case and in the worst case, the result is Theta(log(n)) overall.