3 ms·

Subtle detail of complexity analysis: the input is of length log(n), so taking n^k steps for any positive number k is exponential time.