# What is the time complexity of this nested loop code?

In this loop $$j$$ is dependent on $$i$$, and $$j$$ is executing like $$n/2$$, $$n/2-1$$, $$n/2-2$$, ... So does this sum up to $$O(n\log n)$$?

We just have one comparison when $$n$$ is odd. So, the total complexity is (if we suppose $$n$$ is even, w.l.o.g.):

$$T(n) = \frac{n}{2} + (n +‌ (n-2) + (n-4) + ... + 2)$$ $$= \frac{n}{2} + 2 \sum_{i=1}^{\frac{n}{2}}i = \frac{n}{2} + 2\frac{\frac{n}{2}(\frac{n}{2}+1)}{2} = \Theta(n^2)$$

• j is dependent on i, and j is executing like n/2 , n/2−1, n/2−2 ... isnt it so? – Turing101 Nov 4 '19 at 15:13
• @HIRAKMONDAL How did you get $\frac{n}{2}$? – OmG Nov 4 '19 at 15:15
• for i==0 how many times j loop executes? – Turing101 Nov 4 '19 at 15:18
• @HIRAKMONDAL $n$ times. – OmG Nov 4 '19 at 15:29
• @HIRAKMONDAL Yes. indeed you tried to count the number of printf. – OmG Nov 4 '19 at 15:37