2
$\begingroup$

Is there a method to apply when trying to finding out the time complexity of a piecewise function?

\begin{align*} F(x) &= \begin{cases} 2^x & x < 8, \\ x^2 & x \geq 8. \end{cases} \\ \end{align*}

This case seems straightforward as the function is $\Theta(x^2)$ for a large enough value of $x$, but what should be done in a more complex case... for example a function that gives a result for an odd value of $x$ and another one for an even value of $x$?

$\endgroup$
4
$\begingroup$

There seems to be a misconception here: every function $f$ has a "nice" asymptotic form, in the sense that $f = \Theta(g)$ for some function $g$ given by a reasonable formula. Some examples of reasonable formulas include $c^nn^k\log^\ell n$ for various values of $c,k,\ell$. However, this isn't always the case. Consider for example the function $$ f(n) = \begin{cases} n & \text{if $n$ is odd}, \\ n^2 & \text{if $n$ is even}. \end{cases} $$ There is no "nice" function $g$ such that $f = \Theta(g)$. It is apparent that $f = \Omega(n)$ and that $f = O(n^2)$, but there is no value of $k$ for which $f = \Theta(n^k)$.

In practice, such examples occur only rarely, and so usually it is the case that we can find a nice order of growth for functions that occur in practice.

This discussion is related to another misconception, that we can always compare two functions asymptotically. That is, that for any two functions $f,g$, either $f = o(g)$, or $f = \Theta(g)$, or $f = \omega(g)$. While these three possibilities are indeed mutually exclusive, there is a fourth possibility, namely, that $f$ and $g$ are incomparable. As an example, if we take the function $f$ considered above and try to compare it to $g(n) = n^{3/2}$, then we find that none of $f = o(g)$, $f = \Theta(g)$, $f = \omega(g)$ holds. However, the trichotomy does hold when $f$ and $g$ are "nice" functions (defined using only arithmetic operations, logarithm, and exponential).

Finally, there is one special case which is easy to handle: if $$ f(n) = \begin{cases} g(n) & \text{if } n < C, \\ h(n) & \text{if } n \geq C, \end{cases} $$ Then $f(n) = \Theta(h(n))$. This is the case in your example.

$\endgroup$
  • 1
    $\begingroup$ whoah, great explanation, thank you so much! $\endgroup$ – Vagabond Apr 13 '18 at 10:56

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.