Time complexity of a function

38 Views Asked by At

Can we categorize $f(n)=10+(-1)^n$ as exponential or polynomial ? And how can I compare this function with functions like $g(n)=2^n$ and $h(n)=n^2$ so as to understand if it is greater or not? I know that $f(n)$ equals $11$ or $9$ depending on n's value but how about the time complexity?

1

There are 1 best solutions below

0
On BEST ANSWER

Let $g(n)=1$, then as $$9g(n)\leqslant f(n)\leqslant 11 g(n)$$ for all $n$, it follows that $f\in\Omega(1)$. That is, the time complexity of $f$ is constant.