1

In an article about amortized analysis I found an evaluation$$\frac{n\cdot \Theta (1)+\Theta (n)}{n-1}=\Theta (1).$$ I don't really understand how $\Theta (n)$can be divided by $n-1$ as $n-1$ is not a Big-Theta expression, but just a number, and I didn't find such property.

Can someone explain how$$\frac{\Theta (n)}{n-1}$$evaluates to $\Theta (1)$?

commie trivial
  • 984
  • 2
  • 4
  • 14
B_Junior
  • 13
  • Perhaps it would be best if you post this question on Math Overflow. That site tends to deal with questions regarding research papers or open problems. – MathGeek Jul 27 '22 at 17:16
  • There is some constant $C$ such that $O(n) \leq Cn$ for sufficiently large $n$.

    So $\dfrac{O(n)}{n-1} \leq C\dfrac{n}{n -1} \leq C\Big(1 + \dfrac{1}{n-1}\Big) \leq 2C$.

     – Rishi Jul 27 '22 at 17:20
  • Wait, is theta and O same things or there is difference? I have never heard of theta before. I thought it's sams as O. – Rishi Jul 27 '22 at 17:24
  • @Rishi. Informally, Big Oh $\mathcal{O}$ is an upper bound, Big Omega, $\Omega$ is a lower bound, and Big Theta $\Theta$ is an upper and lower bound. So there is most definitely a difference. For example, $\log(n)$ is in $\mathcal{O}(n)$ but is not in $\Theta(n)$ because $\log(n)$ is asymptotically smaller than $n$. Aka, $\log(n) \not\in \Omega(n)$ – Rodney McCoy Jul 27 '22 at 17:54
  • @RodneyMcCoy So my comment tells that $\dfrac{\Theta(n)}{n - 1}$ is bounded above, right? Showing lower bound should be very similar. – Rishi Jul 27 '22 at 18:07
  • @Rishi. Yes. I think your right. More specifically, the formal definition of $\Theta$ is, given two functions $f$ and $g$. $f \in \Theta(g) \Leftrightarrow f \in \mathcal{O}(g) \land f \in \Omega(g)$. So you showed the upper bound ($\mathcal{O}$), all that is left is to show the lower bound ($\Omega$). – Rodney McCoy Jul 27 '22 at 18:11
  • FYI @Rishi. I thought about your first argument a little more, and I think added steps would make the argument better. Specifically, $C\Big(1 + \dfrac{1}{n-1}\Big) \leq C\Big(1+\dfrac{n-1}{n-1}\Big) = C (1+1) = 2C$ – Rodney McCoy Jul 27 '22 at 19:15

2 Answers2

2

I'm not sure about the exact formal reasoning for this... But since clearly, $n - 1 \in \Theta(n)$, the ratio $\frac{\Theta(n)}{n-1}$ becomes $\frac{\Theta(n)}{\Theta(n)}$. It should make intuitive sense that this ratio is equivalent to $\Theta(1)$.

Why, any function in $\Theta(n)$ is also in $\mathcal{O}(n)$ and $\Omega(n)$. Thus, if $f(n) \in \Theta(n)$, it must be of the form $f(n) = a n + b$ for any non zero scalars $a$ and scalar $b$. If it was asymptotically larger (eg: $n^2, 3^n$), it wouldn't be in $\mathcal{O}(n)$, if it was any asymptotically smaller (eg: $\log(n), 1$), it wouldn't be in $\Omega(n)$. So if we have two arbitrary functions $f_1, f_2 \in \Theta(n)$, there ratio is $\frac{a_1 n + b_1}{a_2 n + b_2} = \frac{a_1 + \frac{b_1}{n}}{a_2 + \frac{b_2}{n}}$. As $n$ gets large, the $\frac{b_1}{n}$ and $\frac{b_2}{n}$ terms approach zero, so we have $\frac{a_1 + 0}{a_2 + 0} = \frac{a_1}{a_2} \in \Theta(1)$

Rodney McCoy
  • 66
0

$\Theta(n)$ can be thought of as representing any function with growth rate $\Theta(n).$ So when someone writes $\Theta(n)/(n-1),$ they mean "a function of the form some $\Theta(n)$ function divided by $n-1.$" But such a function always has growth rate $\Theta(1),$ and so we get the simplification.