I have this question:
Suppose you have a computer that requires 1 minute to solve problem instances of size $n = 7.3000\cdot 10^4$. What instance sizes can be run in 1 minute if you buy a new computer that runs ($4.60\cdot 10^5$) times faster than the old one, if the time complexity is $T(n) = θ(n^2)$.
How do I solve this?
On
You can't solve this problem with just a time complexity. Time complexities tell us how fast the problem grows, but they don't tell us how long the problem actually takes. If $T(n)=\theta(n^2)$, then $T(n)=cn^2+dn$ is a possibility while just $T(n)=cn^2$ is also a possibility. Thus, because you don't actually know $T(n)$, you can't find out exactly how speeding up your computer will affect the size of the problem you can compute.
However, you can approximate the answer to this problem. Let's assume $T(n)=cn^2$. This isn't necessarily true, but assuming this can help us find an easy approximation to this problem. Thus, we know that the old computer can run $T(7.3*10^4)$, or $c(7.3*10^4)^2$, operations in a minute. Since the new computer is $4.6*10^5$ times faster, it can run $c(7.3*10^4)^2*4.6*10^5$ operations in a minute. Now, we need to solve the inequality $T(n) \leq c(7.3*10^4)^2*4.6*10^5$, where we're solving for $n$.
\begin{equation} cn^2 \leq c(7.3*10^4)^2*4.6*10^5 \end{equation} Divide both sides by $c$: \begin{equation} n^2 \leq (7.3*10^4)^2*4.6*10^5 \end{equation} Take the square root of both sides: \begin{equation} n \leq \ \approx 4.95*10^7 \end{equation} Thus, on the new computer, instance sizes up to about $4.95*10^7$ can be solved within a minute.
So $T(n) = cn^2$ so for the current instance you have $c \left( 7.3 \times 10^4 \right)^2$ running in 1 minutes. What is $c$?
Now that you know what $c$ is, how big of an instance will the better computer be able to solve?