0
$\begingroup$

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 Θ(n3) and the input is k2 ?
  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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – David Richerby Sep 6 '16 at 23:06
  • $\begingroup$ 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.) $\endgroup$ – Raphael Sep 6 '16 at 23:19
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.