# Theta Manipulation to show $N = \Theta(n/\log N)=\Theta(n/\log n)$

I am studying different models of computation and how algorithms can be interpreted under different models.

Here is a math(?) question that has been bugging me.

Suppose we have $n = \Theta(N\log N)$ bits as the size of input and there are N elements in the input. (The implied assumption is each element has $\Theta(\log N)$ bits).

Now we know Insertion Sort has running time of $\Theta(N^2)$ in the worst case with respect to N, the number of elements in the input.

Under the RAM model, the input is $n = \Theta(N\log N)$ bits. So we can say $N = \Theta\left(\frac{n}{\log N}\right)$. I want to show that the running time $T = \Theta\left(\frac{n^2}{\log^2n}\right)$ by first showing that $N = \Theta\left(\frac{n}{\log n}\right)$.

Since $N \leq n$, $N = \Theta\left(\frac{n}{\log N}\right)=\Omega\left(\frac{n}{\log n}\right)$. I am having trouble showing $N = \Theta\left(\frac{n}{\log N}\right)= O\left(\frac{n}{\log n}\right)$ to be able to use the $\Theta$ notation.

In general, I am not so sure what kind of manipulations are allowed inside $\Theta$ so that its definition is intact.

$$\frac{n}{\log(n)} = \frac{n}{\log(N\log(N))} = \frac{n}{\log(N)+\log(\log(N))} = \Theta\left(\frac{n}{\log(N)}\right) = O\left(\frac{n}{\log(N)}\right)$$
• I don't see how $\frac{n}{\log(N)+\log(\log(N))} = \Theta\left(\frac{n}{\log(N)}\right)$. I see the lower bound because the denominator of the left side is bigger than the right side, but can't really see how the upper bound can be achieved when the denominator is bigger, hence the whole fraction smaller. There must be a constant $c$ that establishes the upper bound... but I don't really see how it can be done Jan 8 '18 at 12:15
• @namesake22 It is too easy! $\frac{n}{\log(N)+\log(\log(N))} \leq \frac{n}{\log N}$ and $\frac{n}{\log(N)+\log(N)} = 0.5 \frac{n}{\log(N)}\leq \frac{n}{\log(N)+\log(\log(N))}$
• Yes, you're right. I was trying to edit the first comment and I got over the 5 min limit. I didn't see how $\frac{n}{\log(N)+\log(\log(N))} = \Theta\left(\frac{n}{\log(N)}\right)$. I see the lower bound because the denominator of the left side is bigger than the right side. Looking at it more I see the upper bound as well. $\frac{n}{\log(N)} \leq \frac{n}{\log(N^(\frac{1}{2})} = \frac{2}{1}\frac{n}{\log(N)}$. Your idea was very helpful! Jan 8 '18 at 12:22