-5
$\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$
  • $\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 '19 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$ – Sasho Nikolov Oct 3 '19 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 '19 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$ – Sasho Nikolov Oct 4 '19 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 '19 at 19:29
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)$.

| cite | improve this answer | |
$\endgroup$
  • 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$ – Sasho Nikolov Oct 3 '19 at 17:23
  • 4
    $\begingroup$ @SashoNikolov Very small distance to "should not help people cheat" :) $\endgroup$ – Clement C. Oct 3 '19 at 22:29
  • $\begingroup$ @ClementC. lol oops.. $\endgroup$ – Sasho Nikolov Oct 4 '19 at 1:54
  • $\begingroup$ @Denis Ty for the answer. $\endgroup$ – Vk1 Oct 4 '19 at 14:05
-3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ $\log^{c_1} n \log \log^{c_2} n = O(\log^{c_1 + 1} n)$. $\endgroup$ – Huck Bennett Oct 3 '19 at 15:12

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