Runtime Analysis: What grows faster? I was wondering which runtime is a tight upper bound for $f(n,m)= n^2 + 1/2^k$ with $k = n - m$
Intuitively I thought that $f(n,m)$ is in $O(n^2)$ but the longer I am thinking about this the more I tend to say that $f(n,m)$ is in $O(2^k)$.
Can anyone help me?
Since $k=n-m \ge 0$ you have that $n^2 &lt; f(n,m) \le n^2 + (1/2)^0 = n^2+1$, showing that $f(n,m) \in \Theta(n^2)$.