edited by
317 views

1 Answer

0 votes
0 votes

$k\log k = \Theta \left ( n \right )$

$\Rightarrow c1\cdot n \leq   k\log k \leq c2\cdot n$

Now assuming $n$ and $k$ are greater than 1, taking $log$ of each of the terms above will not change the inequality so we can write,

$ \log \left ( c1 \cdot n \right ) \leq   \log\left ( k \cdot \log k \right ) \leq \log\left ( c2\cdot n \right )$

$\Rightarrow \left ( \log \left ( c1 \right ) + \log\left ( n  \right ) \right ) \leq   \left ( \log\left ( k \right ) + \log\left ( \log k \right ) \right ) \leq \left ( \log\left ( c2 \right ) + \log\left ( n \right ) \right )$

Now since we know that

$\log\left ( \log k \right ) \leq  \log\left ( k \right )$

let us write $\left ( \log\left ( k \right ) + \log\left ( \log k \right ) \right ) = 2\log\left ( k \right )$.

To maintain the inequality,

$\left ( \log\left ( k \right ) + \log\left ( \log k \right ) \right ) \leq \left ( \log\left ( c2 \right ) + \log\left ( n \right ) \right )$,

after changing $\left ( \log\left ( k \right ) + \log\left ( \log k \right ) \right )$ to $2\log\left ( k \right )$,

we should multiply $\left ( \log\left ( c2 \right ) + \log\left ( n \right ) \right )$ by $2$, to compensate the increment in the middle term.

   $\Rightarrow \left ( \log \left ( c1 \right ) + \log\left ( n  \right ) \right ) \leq  2\log\left ( k \right ) \leq 2\left ( \log\left ( c2 \right ) + \log\left ( n \right ) \right )$

To make this inequality more clear let's write it using new constants as follows,

$c3 \left ( \log \left ( n \right ) \right ) \leq c4 \left ( \log \left ( k \right ) \right ) \leq c5 \left ( \log \left ( n \right ) \right )$

On dividing $ c1\cdot n \leq   k\log k \leq c2\cdot n$  by the above inequality we get,

$\left ( \frac{c1}{c3} \right ) \left ( \frac{n}{\log\left ( n \right )} \right ) \leq \left ( \frac{1}{c4} \right )\left ( \frac{k\log k}{\log\left ( k \right )} \right ) \leq \left ( \frac{c2}{c5} \right )\left ( \frac{n}{\log\left ( n \right )} \right )$.

$\Rightarrow \left ( \frac{c1}{c3} \right ) \left ( \frac{n}{\log\left ( n \right )} \right ) \leq \left ( \frac{1}{c4} \right )k \leq \left ( \frac{c2}{c5} \right )\left ( \frac{n}{\log\left ( n \right )} \right )$

$\Rightarrow \left ( \frac{c1 \cdot c4}{c3} \right ) \left ( \frac{n}{\log\left ( n \right )} \right ) \leq k \leq \left ( \frac{c2 \cdot c4}{c5} \right )\left ( \frac{n}{\log\left ( n \right )} \right )$

$\Rightarrow k = \Theta \left ( \frac{n}{\log\left ( n \right )} \right )$.


PS - I am not very sure about the inequalities division step.

Related questions

538
views
0 answers
0 votes
kira000 asked Jan 17, 2023
538 views
Let $f(n)$ be a positive increasing function. Consider the below two statements:S1: if an algorithm is $\Theta(f(n))$ in the average case, then it is $\Omega(f(n))$ ... $g(n)$ belongs to the set $\Theta(f(n))$, right?