0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

There is not any strange thing here. As:

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

Therefore, all of them are true.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – namesake22
    Commented Jan 8, 2018 at 12:15
  • 1
    $\begingroup$ @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))} $ $\endgroup$
    – OmG
    Commented Jan 8, 2018 at 12:20
  • $\begingroup$ 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! $\endgroup$
    – namesake22
    Commented Jan 8, 2018 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.