<p><span class="math-container">$(\log n)^{\log(\log n)}$</span> i.e. <span class="math-container">$2^{(\log(\log n))^2}$</span>.</p>

<p>It is not in <span class="math-container">$O(\log^d n)$</span> because <span class="math-container">$\log(\log n)$</span> is not in <span class="math-container">$O(1)$</span>.</p>

<p>It is in <span class="math-container">$o(n^c)=o(2^{c\log n})$</span> because the exponent <span class="math-container">$(\log(\log n))^2$</span> is in <span class="math-container">$o(\log n)$</span>.</p>

CC BY-SA 4.0
2019-10-03T17:23:48.753Z
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.
Sasho Nikolov
CC BY-SA 4.0
2019-10-03T22:29:59.947Z
@SashoNikolov Very small distance to "should **not** help people cheat" :)
Clement C.
CC BY-SA 4.0
2019-10-04T01:54:40.530Z
@ClementC. lol oops..
Sasho Nikolov
CC BY-SA 4.0
2019-10-04T14:05:11.890Z
@Denis Ty for the answer.
Vk1
CC BY-SA 4.0
2019-10-03T12:13:41.370Z
2019-10-03T12:13:41.370Z
Denis
<p><span class="math-container">$O(\log^{c_1}n\log\log^{c_2}n)$</span> would be an option.</p>

CC BY-SA 4.0
2019-10-03T15:12:35.113Z
$\log^{c_1} n \log \log^{c_2} n = O(\log^{c_1 + 1} n)$.
Huck Bennett
CC BY-SA 4.0
2019-10-03T10:41:28.337Z
2019-10-03T10:41:28.337Z
Sudipta Roy
<p><span class="math-container">$O(n^c)$</span> is asymptotically greater than <span class="math-container">$O(\log^d n) $</span> for all possible pair of values of <span class="math-container">$c$</span> and <span class="math-container">$d$</span>. </p>

<p>Can you give an example of a problem (or data structure) which has running time (or query/update time) <span class="math-container">$f(n)$</span> </p>

<p>such that <span class="math-container">$f(n)$</span> is asymptotically larger than <span class="math-container">$O(\log^d n)$</span> but asymptotically smaller than <span class="math-container">$O(n^c)$</span> for all values of <span class="math-container">$c$</span> and <span class="math-container">$d$</span>?</p>

CC BY-SA 4.0
2019-10-03T13:20:00.977Z
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}}$.
R B
CC BY-SA 4.0
2019-10-03T17:22:49.343Z
@RB you are answering someone's homework question. I'd rather we didn't help people cheat in their courses.
Sasho Nikolov
CC BY-SA 4.0
2019-10-04T15:59:16.090Z
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.
Vk1
CC BY-SA 4.0
2019-10-04T17:42:58.613Z
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.
Sasho Nikolov
CC BY-SA 4.0
2019-10-04T19:29:06.097Z
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](https://cs.stackexchange.com/).
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.
Clement C.
CC BY-SA 4.0
2019-10-04T23:46:30.940Z
Meta thread: https://cstheory.meta.stackexchange.com/q/3046/1993
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2019-10-05T00:15:06.110Z
I rolled this back to version 1 since the other comments probably belong on https://cstheory.meta.stackexchange.com/
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2019-10-05T03:15:20.280Z
It may be quite easy to conjure up a function between those two functions... But no one I encountered could come up with a simple problem which would have such a running time, in other words a problem which had its running time between these two bounds. That was the beauty I was seeking here. That was the Theoretical Comp science research level answer I was seeking?

Is the following question still research level or first year under grad level?

Can you phrase a problem which requires super poly logarithmic running time, but is $o(n^c)$ in running time?
Vk1
CC BY-SA 4.0
2019-10-05T04:37:30.893Z
I understand that this question may be slightly off the TCS boards, but I dont see why people bother so much about whether its is assignment or not. Please stop bothering about this. 

All of you have been students and all of you know that if a student is hell bent of cheating he will find a way out.


You cant stop him from cheating. He will not hesitate from asking peers, seniors etc. 
If he posts on stackexchange, at least this way he learns something from you and he can be sure that the community is guiding him in the right way.
Vk1
<time-complexity>
A sandwich Algorithm / Data Structure
Vk1
# A sandwich Algorithm / Data Structure

(Asked by: username_0 on 2019-10-03)

$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$?

**Tags:** time-complexity
> **Comments:**
> **username_1**: 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}}$.  
> **username_2**: @RB you are answering someone's homework question. I'd rather we didn't help people cheat in their courses.  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_3**: 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](https://cs.stackexchange.com/). 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.  
> **username_4**: Meta thread: https://cstheory.meta.stackexchange.com/q/3046/1993  
> **username_4**: I rolled this back to version 1 since the other comments probably belong on https://cstheory.meta.stackexchange.com/  
> **username_0**: It may be quite easy to conjure up a function between those two functions... But no one I encountered could come up with a simple problem which would have such a running time, in other words a problem which had its running time between these two bounds. That was the beauty I was seeking here. That was the Theoretical Comp science research level answer I was seeking?  Is the following question still research level or first year under grad level?  Can you phrase a problem which requires super poly logarithmic running time, but is $o(n^c)$ in running time?  
> **username_0**: I understand that this question may be slightly off the TCS boards, but I dont see why people bother so much about whether its is assignment or not. Please stop bothering about this.   All of you have been students and all of you know that if a student is hell bent of cheating he will find a way out.   You cant stop him from cheating. He will not hesitate from asking peers, seniors etc.  If he posts on stackexchange, at least this way he learns something from you and he can be sure that the community is guiding him in the right way.  

---

## 2 answers

### Answer by username_5 on 2019-10-03. Score: 4

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

> **Comments:**
> **username_2**: 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.  
> **username_3**: @SashoNikolov Very small distance to "should **not** help people cheat" :)  
> **username_2**: @ClementC. lol oops..  
> **username_0**: @Denis Ty for the answer.  

---

### Answer by username_6 on 2019-10-03. Score: -3

$O(\log^{c\_1}n\log\log^{c\_2}n)$ would be an option.

> **Comments:**
> **username_7**: $\log^{c_1} n \log \log^{c_2} n = O(\log^{c_1 + 1} n)$.  

---

