Skip to main content
Computer Science

Return to Answer

deleted 1 character in body
Source Link
R B
R B
  • 2.6k
  • 16
  • 35

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 $N\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor$$\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)$$

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

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

deleted 52 characters in body
Source Link
R B
R B
  • 2.6k
  • 16
  • 35

Not that I encourage you to do so, but here's one way: $$\Theta \left(N\left\lfloor\log\left(\frac{1}{N\epsilon}\right)+1\right\rfloor+ \frac{1}{\epsilon+N^{-1}}+\log N\right) $$$$\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 $N\left\lfloor\log\left(\frac{1}{N\epsilon}\right)+1\right\rfloor$$N\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\left\lfloor\log\left(\frac{1}{N\epsilon}\right)+1\right\rfloor+ \frac{1}{\epsilon+N^{-1}}+\log N\right) = \Theta\left(N\left\lfloor\log\left(\frac{1}{N\epsilon}\right)+1\right\rfloor+\Theta(N)\right)=\Theta\left(N\log\frac{2}{N\epsilon}\right)$$$$\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)$$

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

For $\epsilon = \omega(N^{-1})$, the $N\left\lfloor\log\left(\frac{1}{N\epsilon}\right)+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\left\lfloor\log\left(\frac{1}{N\epsilon}\right)+1\right\rfloor+ \frac{1}{\epsilon+N^{-1}}+\log N\right) = \Theta\left(N\left\lfloor\log\left(\frac{1}{N\epsilon}\right)+1\right\rfloor+\Theta(N)\right)=\Theta\left(N\log\frac{2}{N\epsilon}\right)$$

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

Post Undeleted by R B
Post Deleted by R B
added 8 characters in body
Source Link
R B
R B
  • 2.6k
  • 16
  • 35

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

For $\epsilon = \omega(N^{-1})$, the $N\left\lfloor\log\left(\frac{1}{N\epsilon}\right)\right\rfloor$$N\left\lfloor\log\left(\frac{1}{N\epsilon}\right)+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\left\lfloor\log\left(\frac{1}{N\epsilon}\right)\right\rfloor+ \frac{1}{\epsilon+N^{-1}}+\log N\right) = \Theta\left(N\left\lfloor\log\left(\frac{1}{N\epsilon}\right)\right\rfloor+\Theta(N)\right)=\Theta\left(N\log\frac{2}{N\epsilon}\right)$$$$\Theta \left(N\left\lfloor\log\left(\frac{1}{N\epsilon}\right)+1\right\rfloor+ \frac{1}{\epsilon+N^{-1}}+\log N\right) = \Theta\left(N\left\lfloor\log\left(\frac{1}{N\epsilon}\right)+1\right\rfloor+\Theta(N)\right)=\Theta\left(N\log\frac{2}{N\epsilon}\right)$$

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

For $\epsilon = \omega(N^{-1})$, the $N\left\lfloor\log\left(\frac{1}{N\epsilon}\right)\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\left\lfloor\log\left(\frac{1}{N\epsilon}\right)\right\rfloor+ \frac{1}{\epsilon+N^{-1}}+\log N\right) = \Theta\left(N\left\lfloor\log\left(\frac{1}{N\epsilon}\right)\right\rfloor+\Theta(N)\right)=\Theta\left(N\log\frac{2}{N\epsilon}\right)$$

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

For $\epsilon = \omega(N^{-1})$, the $N\left\lfloor\log\left(\frac{1}{N\epsilon}\right)+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\left\lfloor\log\left(\frac{1}{N\epsilon}\right)+1\right\rfloor+ \frac{1}{\epsilon+N^{-1}}+\log N\right) = \Theta\left(N\left\lfloor\log\left(\frac{1}{N\epsilon}\right)+1\right\rfloor+\Theta(N)\right)=\Theta\left(N\log\frac{2}{N\epsilon}\right)$$

added 10 characters in body
Source Link
R B
R B
  • 2.6k
  • 16
  • 35
Source Link
R B
R B
  • 2.6k
  • 16
  • 35