1

Can you help me to find Omega, Theta, and Big O notations for the following equation?

$T(n)=\left(\frac{n+3}{n}\right)^n$

I have tried this, but I'm unsure if I'm moving in the right direction to solve it.

For Big-O notation..

$$0\leq T(n)\leq c \cdot g(n)$$

$$0\leq \left(\frac{n+3}{n}\right)^n \leq n^n$$

$$O(n^n) \forall n \geq 3$$

For $\Omega$ Notation..

$$0 \leq c\cdot g(n) \leq T(n) $$

$$ 0 \leq n^n \leq \left(\frac{n+3}{n}\right)^n$$

$$\Omega(n^n) \forall 0 < n < 3$$

Is it right? Help me with this.

Aman Rangapur
  • 11
  • $n^n \leq \left(\frac{n+3}{n}\right)^n$ ????? – EnEm Sep 26 '22 at 21:31
  • Revise the definitions please and look at a couple of examples to understand what does these notations mean. You've written $\Omega(n^n) \forall 0 < n < 3$, but that's not how these notations work. We say functions are big O, small o, big Omega, small omega and Theta $\textbf{asymptotically}$, which generally means that the conditions are true for $\textbf{large }$ $N$ (specifically $\forall n\ge n_0$ for some $n_0$) – EnEm Sep 26 '22 at 21:37
  • Also that condition isn't even true for $0<n<3$, https://www.desmos.com/calculator/izefp6mnwh . Not that it matters here – EnEm Sep 26 '22 at 21:40
  • @EnEm, I have recaptured the basics of asymptotic notations, but I'm still finding it hard to solve the $\Omega$ notation for this particular recurrence. Can you give a hint so that I can work on solving it? – Aman Rangapur Sep 27 '22 at 15:44
  • How did you solve for the $\Theta$ notation? – EnEm Sep 27 '22 at 16:03
  • @EnEm, using the limits that you mentioned earlier. Using this as a reference(https://web.mit.edu/broder/Public/asymptotics-cheatsheet.pdf). But the problem I'm facing is with the $n_{0}$ value for $\Omega$ notation. – Aman Rangapur Sep 27 '22 at 16:37
  • So you were able to find $n_0,c_1,c_2$ such that $c_1g(n)\le f(n) \le c_2 g(n) :\forall n_0\ge n$ but can't find an $n_0,c$ such that $cg(n)\le f(n) \forall :n_0\ge n$ ?? – EnEm Sep 27 '22 at 16:55
  • @EmEn Oh shit, I'm yet to find c1, c2. I wrote the normal form for $\Theta$ notation. I made a mistake while finding $\Theta$ notation. – Aman Rangapur Sep 27 '22 at 18:14
  • Ok, hint for all three $\Omega, O and \Theta$ , use $g(n) = 1$ – EnEm Sep 27 '22 at 18:25
  • @EnEm, For $\Omega$, $(1+\frac{3}{n})^{n}>1$, $n_{0} \geq 1$ where $c$ is $1$. Therefore $\Omega(log n)$ Is this right? For $\Theta$ notation please look at this(https://www.desmos.com/calculator/spobjrazii) – Aman Rangapur Sep 27 '22 at 22:17
  • $\Omega(1)$, Also you can't put $c_1 = 0$, it should be $>0$. Also your $c_2$ doesn't work for large n. Check this https://www.desmos.com/calculator/lejfplt5am – EnEm Sep 28 '22 at 08:32

1 Answers1

0

Although your big O complexity is correct, it isn't the tightest bound, and hence you cannot get the Theta complexity using that.

The key hint is to use the limit $\lim_{n\to\infty}\left(\frac{n+3}{n}\right)^n=\lim_{n\to\infty}\left(1+\frac{3}{n}\right)^n=e^3$, using which you can prove that this is actually $\Theta(1)$

EnEm
  • 656
  • Hey @EnEm, can you please look at the Omega notation? Also, is there any way to find Theta notation without using limits? – Aman Rangapur Sep 26 '22 at 18:58
  • @AmanRangapur Theta is just Omega + Big O, You cant get to Theta without Omega. With the limit Im not just finding out the Theta, Im also finding the Omega and big O, and using it you find the Theta. Revise the definitions for these notations once. For your second part, I guess you can just prove that T(n) is bounded and that would be enough, no need to show that it is converging too, and whats its converging to. You can do this by simply showing $T(n)\leq\sum_{k=0}^n\frac{3^k}{k!} \forall n$ – EnEm Sep 26 '22 at 21:25
  • @AmanRangapur Ohh you meant the edit you did in your original question, sorry I didn't see that. I'll respond it to now. – EnEm Sep 26 '22 at 21:30