Determine time given algorithmic complexity as input grows?

Question

Consider the time required to solve a problem, represented by f(n), and for sufficiently large inputs of size k, the time required to solve a problem is t. What is the typical method of determining how long, in terms of t, is necessary to solve a problem, for different kinds of f(n) and k?

For example, when f(n) is Θ(n), and the input is 2k, we know that the time is approximately 2t. But what is the standard method of determining the time, in terms of t, for problems like this? For example:

1. When f(n) is Θ(n³) and the input is k² ?
2. f(n) is Θ(2n) and the input size is k+3 ?
3. f(n) is Θ(lg n) and the input size is 4k ?
4. f(n) is Θ(n!) and the input size is k+2 ?

This question is not asking for answers to those scenarios per se, rather, how to go about expressing the time, in terms of t, given the parameters above.

• David Richerby: I don't understand what you're asking. You seem to be asking, "If $f$ is some function and $n$ is some function of $k,ドル what is $f(n)$ in terms of $k$?" If that's what you are asking, I don't understand why you don't just substitute the function of $k$ for $n$ to get your answer.
• Raphael: This has nothing to do with algorithm analysis, and everything with understanding the definitions of Landau notation. (Landau terms tell you very little about actual running times.)

Answer 1

The standard method is to heuristically assume that a bound of the form $\Theta(g(n))$ can be approximated by $Cg(n)$ for some constant $C,ドル though in some cases this approximation is not justified, and the "constant" $C$ fluctuates (but is bounded on both sides).

Considering your first example, if $f(n) \approx Cn^3$ then $f(k^2) \approx Ck^6 = (Ck^3)^2/C \approx f(k)^2/C$. Unfortunately, the dependence on $C$ cannot be eliminated, but $C$ can be approximated empirically, though you should take such results with a grain of salt.