Consider ``padding'' out the input with infinities to make n a power of 2. How does this affect the running time?