Computing 2 ^ n in O (n) time

Question

Without using bit shifts, is there a way to compute 2 ^ n in O (n) time?

I was considering a solution using memoization, as I will always calculate first from n. i.e

d = dict()
def pwr2(n):
    if n == 0:
       return 1
    if n == 1:
       return 2
    if n in d:
       return d[n]
    d[n] = 2 * pwr2(n-1)
    return d[n]

But I'm not quite sure what the difficulty will be.

EDIT: I have to add that I use this part of the algorithm to convert binary to decimal faster than O (n ^ 2). As part of my separation and dormant algorithm, I have to multiply, increasing powers by two, so I tried using memoizing.

EDIT2: just submit my complete algorithm here to help eliminate the confusion pwr2dict = dict ()

def karatsuba(x, y):
    // use karatsuba algorithm to multiply x*y


def pwr2(n):
    if n == 0:
        return 1
    if n == 1:
        return 2
    if n in pwr2dict:
        return pwr2dict[n]
    pwr2dict[n] = karatsuba(pwr2(n-1),2)
    return pwr2dict[n]


def binToDec(b):
    if len(b) == 1:
        return int(b)
    n = int(math.floor(len(b)/2))
    top = binToDec(b[:n])  # The top n bits
    bottom = binToDec(b[n:])  # The bottom n bits
    return bottom + karatsuba(top, pwr2(len(b)-n))

print binToDec("10110") // Prints 22

Answer 1

, . 2^n n . , 1 n : -)

r = 2
for 1 to n do
  r = r * 2
end

, O(n), 2^n, , n, 32, 64 128. , O(n), :-) O(n).

, , , , .

:

n , s ( , , , ). , LSB 0 ( ).

e := 1
r := 0
for i := 0 to (n - 1) 
  if s[i] = 1
    r := r + e
  end
  e := e * 2
end

O(n), 0 n - 1, O(n). . , r .

Answer 2

O (1) . 2 n-1 . 1 n .

. long k = 2 << n-1. long k = 1 << n.

?

, . O (n). O (logn)

private int power(int x, int n) {

    if (n == 1)
        return x;
    if (n % 2 == 0) {
        int power = power(x, n / 2);
        return power * power;
    } 

    else{
        int power = power(x, (n - 1) / 2);
        return x * power * power;
    }
}

Answer 3

Time = T(f(n)) + T(g(n)), f(n) - , n, g(n) - , .

public BigInteger pow_2 (int n)
{
    String binary = "1";
    for (int i=0; i<n; i++) binary += "0"; // f(n)
    return new BigInteger(binary, 2); // g(n)
}

- f(n) T(f(n)) Θ(1).

g(n), BigInteger(value,radix), g(n) , , 2^n - n+1 .