Say I have some problem of $O\left(n^k\right)$ complexity.
If I were to solve the problem on a computer $x$, it would take time $t$.
Now I have a new computer $x'$, which has double the computing power of $x$.
How long would it take $x'$ to solve the same problem in terms of $t$?
It will take half the time of course, $t'=t/2$, and the asymptotic complexity remains $O(n^k)$ !
Comment: This actually answers a much more interesting question:
Suppose algorithm $A$ runs in time $O(n^k)$ on inputs of length $n$. If we double the input length, how long would it take $A$ to run on the new input in terms of its running time on the original output?
The answer you were supposed to give is:
$2^kT$, where $k$ is the exponent in the running time $O(n^k)$.
The idea is that if your running time is exactly $T(n) = Cn^k$ then $$ T(2n) = C(2n)^k = 2^k(Cn^k) = 2^kT(n). $$
However, the running time need not be exactly $Cn^k$, and if it isn't, you can't really tell what the exact relation is between $T(2n)$ and $T(n)$. You can come up with pathological examples like $$ T(n) = \begin{cases} 1 & \text{if $n$ is odd}, \\ n & \text{if $n$ is even}. \end{cases} $$ If $n$ is odd then $T(2n) = 2nT(n)$, and the factor $2n$ isn't bounded; yet $T(n) = O(n)$ has polynomial growth.
If $T(n) = \Theta(n^k)$ then we can say that $T(2n) = \Theta(T(n))$, but it could still be that, say, $T(2n) < T(n)$, as in this examples: $$ T(n) = \begin{cases} 100n & \text{if $n$ is odd}, \\ n & \text{if $n$ is even}. \end{cases} $$ If $n$ is odd then $T(2n) = T(n)/50$.
