Combining these two results into one asymptotic notation

Question

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.

Answer 1

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)$$

Answer 2

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).$