0

Given two functions $f(k)=2k+log_2(k+1)$ and $f'(k)=k+log_2(k)$, I am wondering how far $f(k)$ is to $f'(k)$ in asymptotic notation. If $k$ is large then $log_2(k)\approx log_2(k+1)$ and $f(k)=f'(k)+k$. Does that mean $f(k)$ is $O(k)$ far from $f'(k)$ ?

I assume $f(x)$ being $O(k)$ far from $f'(k)$ means $f'(k)$ should be multiplied (not summed) by $k$. IF that's true then is it $O(1)$?

seteropere
  • 627
  • 2
    I think what you really want to say is that $f(k)-f'(k)=\Theta(k)$, which is indeed true, since $f(k)-f'(k)=k+\log_2(k+1)-\log_2(k)$, hence $k \leq f(k)-f'(k) \leq k+\frac{1}{k \ln(2)}$ (using concavity of the logarithm). If you are instead talking about ratios, then $\frac{f(k)}{f'(k)}=\Theta(1)$. (If you don't recognize the notation, look up Big Theta notation, it is a variant of Big Oh notation which is more precise.) – Ian Jan 01 '16 at 19:43
  • @Ian Thanks. I am making my way into the notations and know Big theta means bounded from above and below. $f'(x)$ is the best function could possibly exist. I would think ratio isn't applicable here. Please turn your comment to an answer. – seteropere Jan 01 '16 at 19:55

1 Answers1

2

I think what you really want to say is that $f(k)−f′(k)=Θ(k)$, which is indeed true, since $f(k)−f′(k)=k+\log_2(k+1)−\log_2(k)$, hence $k \leq f(k)−f′(k)≤k+\frac{1}{k \ln(2)}$ (using concavity of the logarithm). If you are instead talking about ratios, then $\frac{f(k)}{f'(k)}=\Theta(1)$. (If you don't recognize the notation, look up Big Theta notation, it is a variant of Big Oh notation which is more precise.)

Ian
  • 101,645