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:
- When f(n) is Θ(n3) and the input is k2 ?
- f(n) is Θ(2n) and the input size is k+3 ?
- f(n) is Θ(lg n) and the input size is 4k ?
- 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.