Complexity calculation by using sum notation

Question

I have 3 loops and I've written them using sigma notation. However, I cannot go further. I want to get its result as Big-Oh. Can you help? $$ \sum _{i=1}^{\frac{n}{2}}\:\sum _{j=1}^{\lceil\log n\rceil}\sum _{k=1}^{\lceil\log j\rceil}1 = \sum _{i=1}^{\frac{n}{2}}\:\sum _{j=1}^{\lceil\log n\rceil}\lceil\log j\rceil $$

Answer 1

As it's asymtotic, we can ignore $\lceil \cdot \rceil$ function here w.l.o.g. $$S = \sum _{i=1}^{\frac{n}{2}}\:\sum _{j=1}^{\lceil\log n\rceil}\sum _{k=1}^{\lceil\log j\rceil}1 = \sum _{i=1}^{\frac{n}{2}}\:\sum _{j=1}^{\lceil\log n\rceil}\lceil\log j\rceil \approx \sum _{i=1}^{\frac{n}{2}}\:\sum _{j=1}^{\log n}\log j = \sum _{i=1}^{\frac{n}{2}}\log(\log(n)!)$$

To know more why $\sum _{j=1}^{\log n}\log j = \sum _{i=1}^{\frac{n}{2}}\log(\log(n)!)$: $$\sum _{j=1}^{\log n}\log j = \log(1) + \log(2) + \cdots + \log(\log(n)) = \log(1\times 2 \times \cdots\times \log(\log(n)) = \log(\log(n)!)$$

Hence, as we know $n! = O(n^n)$, we can say $\log(\log(n)!) = O(\log(\log(n)^{\log(n)})) = O(\log(n)\log(\log(n))) $. Therefore, $$S = \sum _{i=1}^{\frac{n}{2}}O(\log(n)\log(\log(n))) = O(n\log(n)\log(\log(n))$$

If the inner sum is $i$ instead of $n$ we will have: $$S = \sum _{i=1}^{\frac{n}{2}}O(\log(i)\log(\log(i))) \leq O(\log(\log(n))(\sum _{i=1}^{\frac{n}{2}}O(\log(i)))) \Rightarrow S = O(n\log(n)\log(\log(n))$$