Assume you have two parameters, $N \gg 1$ and $\epsilon < 1$.

I have an algorithm (and matching lower bounds) that runs in $\Theta(\epsilon^{-1}+\log N)$ for $\epsilon > N^{-1}$, and $\Theta\big(N\log\big(\frac{2}{N\epsilon}\big)\big)$ otherwise.

I would like to write it using one notation (possibly with $\max$ or $\min$ operands), but can't get it right.

The problem is that $\log\big(\frac{2}{N\epsilon}\big)$ is negative for large values of $\epsilon$, so it doesn't seem to fit.

Any help will be appreciated :D.

  • 4
    $\begingroup$ Don't convert it into one asymptotic notation. $\endgroup$ – Yuval Filmus Jul 7 '15 at 21:43

Not that I encourage you to do so, but here's one way: $$\Theta \left(N\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor+ \frac{1}{\epsilon+N^{-1}}+\log N\right) $$

For $\epsilon = \omega(N^{-1})$, the $\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor$ expression is $0$, and the left expression is $$\frac{1}{\epsilon+N^{-1}}+\log N = \Theta(\epsilon^{-1} + \log N)$$

For $\epsilon = \Theta(N^{-1})$, the whole expression translates into $\Theta(N)$.

For $\epsilon = o(N^{-1})$ you get: $$\Theta \left(N\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor+ \frac{1}{\epsilon+N^{-1}}+\log N\right) = \Theta\left(N\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor+\Theta(N)\right)=\Theta\left(N\log\frac{2}{N\epsilon}\right)$$


Which asymptote do you want?

If you fix $\epsilon$ to be constant and let $N\to\infty,$ then asymptotically $\epsilon > N^{-1},$ and so the behavior is $\Theta(\epsilon^{-1} + \log N) = \Theta(\log N).$

  • 2
    $\begingroup$ I don't think OP sees $\epsilon$ as a constant.. $\endgroup$ – R B Jul 10 '15 at 8:00

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.