# Tag Info

1

As it come out from comments we are talking about book Stefan Hougardy, Jens Vygen - Algorithmic Mathematics-Springer International Publishing (2016), where algorithm in question is on page 8. Confusing moment from page 10 " ..the number of steps performed by the algorithm is also never less than $\sqrt{n}$ " can be explained from page 9 It is ...

1

We can simplify $t_b(n):$ $$t_b(n) =2^{\sqrt{\log _{2}n}}$$ $$=\left(2^{\log _{2}n}\right)^{\frac{1}{\sqrt{\log _{2}n}}}$$ $$=\left(n^{\log _{2}2}\right)^{\frac{1}{\sqrt{\log _{2}n}}}$$ $$=n^{{\frac{1}{\sqrt{\log _{2}n}}}}$$ $$=\sqrt[\sqrt{\log_2 n}]{n}.$$ Therefore $$\left(\sqrt[\sqrt{\log_2 n}]{n}\right)=\mathcal{O}\left(\sqrt{n}\right)$$ because \...

2

You are looking at worst-case analysis in your book, i.e. how many steps does the algorithm perform in the worst-case. So the statement should at least be amended to say One can even say in this case that the algorithm has running time $\Theta(\sqrt n)$, because the number of steps performed by the algorithm in worst-case is also never less than $\sqrt n$ ...

1

Below method, solve your problem in $\mathcal{O}(n)$, and additional space $\mathcal{O}(n)$. Use Selection algorithm to find $(\log n)^{th}$ largest element in worst case $\mathcal{O}(n)$. Then your array become below form : That we partition the array in term of $(\log n)^{th}$ largest element. Now all elements in $L$ are greater equal to $(\log n)^{th}$ ...

2

It just means that the condition $0 \le c_1 g(n) \le f(n) \le c_2 g(n)$ only needs to hold for large enough integers. This allows you to ignore all integers that are smaller than $n_0$ so you can just pick $n_0$ as large as needed for the inequalities to hold. Notice that you do not need to pick $n_0$ as the smallest integer with that property, so you might ...

Top 50 recent answers are included