-4
$\begingroup$

$O(n^c)$ is asymptotically greater than $O(\log^d n) $ for all possible pair of values of $c$ and $d$.

Can you give an example of a problem (or data structure) which has running time (or query/update time) $f(n)$

such that $f(n)$ is asymptotically larger than $O(\log^d n)$ but asymptotically smaller than $O(n^c)$ for all values of $c$ and $d$?

$\endgroup$
9
  • $\begingroup$ You have $n^c=e^{c\log n}$ and $\log^d n = e^{d\log\log n}$. So you can take anything in $e^{o(\log n)}\cap e^{\omega(\log\log n)}$, e.g., their geometric mean $e^{\sqrt{\log n \log\log n}}$. $\endgroup$
    – R B
    Oct 3, 2019 at 13:20
  • 2
    $\begingroup$ @RB you are answering someone's homework question. I'd rather we didn't help people cheat in their courses. $\endgroup$ Oct 3, 2019 at 17:22
  • 1
    $\begingroup$ I added some thoughts for you guys to reflect on. FYI:- If I had to clear an assignment I would have gone to Quora. I came here because I thought that some great minds might enlighten me with something unusual and beautiful. Unfortunately these great minds are too busy trying to figure out whether this is an assignment or not. Such a pity. $\endgroup$
    – Vk1
    Oct 4, 2019 at 15:59
  • 1
    $\begingroup$ This is on the level of an undergraduate homework question, and is a very typical homework question in an intro course. You do not need any great minds to answer it, and it is most definitely off topic here. Perhaps Quora was the right choice for you. $\endgroup$ Oct 4, 2019 at 17:42
  • 1
    $\begingroup$ Ignoring the passive-aggressiveness, @Vk1: if it's not a homework, it's still not research-level in theoretical computer science, and would then fall under the umbrella of CS.SE. Not ignoring the passive-agressiveness: as originally framed, your question was literally indistinguishable from someone asking for homework answers. If it quacks like a duck, you can't blame anyone for not thinking it's a zebra. $\endgroup$
    – Clement C.
    Oct 4, 2019 at 19:29

2 Answers 2

4
$\begingroup$

$(\log n)^{\log(\log n)}$ i.e. $2^{(\log(\log n))^2}$.

It is not in $O(\log^d n)$ because $\log(\log n)$ is not in $O(1)$.

It is in $o(n^c)=o(2^{c\log n})$ because the exponent $(\log(\log n))^2$ is in $o(\log n)$.

$\endgroup$
4
  • 4
    $\begingroup$ Please see my comment to the question. (1) We should not answer off-topic questions, which this one surely is. (2) We should help people cheat on their homeworks. $\endgroup$ Oct 3, 2019 at 17:23
  • 4
    $\begingroup$ @SashoNikolov Very small distance to "should not help people cheat" :) $\endgroup$
    – Clement C.
    Oct 3, 2019 at 22:29
  • $\begingroup$ @ClementC. lol oops.. $\endgroup$ Oct 4, 2019 at 1:54
  • $\begingroup$ @Denis Ty for the answer. $\endgroup$
    – Vk1
    Oct 4, 2019 at 14:05
-3
$\begingroup$

$O(\log^{c_1}n\log\log^{c_2}n)$ would be an option.

$\endgroup$
1
  • $\begingroup$ $\log^{c_1} n \log \log^{c_2} n = O(\log^{c_1 + 1} n)$. $\endgroup$ Oct 3, 2019 at 15:12

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