# Time complexity of a function with while loop

What is the time complexity of the following procedure?

for $$x \in \{1,\ldots,n\}$$:
$$\quad$$ $$i \gets \lfloor n/2 \rfloor$$
$$\quad$$ while $$i \neq x$$:
$$\quad\quad$$ if $$i > x$$ then $$i \gets i -1$$, otherwise $$i \gets i + 1$$.

According to me, the time complexity is $$O(n^2)$$. The inner while loop starts at $$n/2$$ and moves towards the value of $$x$$, worst case it runs $$n/2$$ times, and best case it runs $$0$$ times.

What is the exact time complexity of this procedure?

• cs.stackexchange.com/q/23593/755
– D.W.
Apr 10 at 6:25
• Yes, but I want to know if my intuition is correct?
– kiv
Apr 10 at 6:28
• I suggest following the systematic methodology there, then editing your question to show your work. That's how you can verify your intuition.
– D.W.
Apr 10 at 6:30
• Please, post text as text, not as photographs of text. This is not a website for photographers who want to critique your use of color and perspective. It should be possible to copy&paste your text. It also makes your question unreadable to the blind and visually impaired. It also makes it impossible to index both by Stack Exchange's own search engine as well as Google, Bing, and co. Apr 10 at 11:44

Assume $$\frac{N}{2}\in\mathbb{N}$$, $$\frac{N}{2}+(\frac{N}{2}-1)+\cdots+1+0+1+\cdots +(\frac{N}{2}-1)=\frac{N}{2}+2\times\sum_{k=1}^{N/2-1}k=\frac{N}{2}+\frac{N^2-2N}{4}=\frac{N^2}{4}\in O(N^2)$$
• That equation cannot be true (although the sums is indeed in $O(N^2$). Apr 10 at 15:58
The while loop runs for $$|x - \lfloor n/2 \rfloor|$$ many iterations. Therefore the running time is proportional to $$\sum_{x=1}^n |x - \lfloor n/2 \rfloor|.$$ To ease the calculation a bit, let us assume that $$n$$ is even. We break the sum into two parts: $$\sum_{x=1}^{n/2} (n/2 - x) + \sum_{x=n/2+1}^n (x - n/2) = \sum_{x=0}^{n/2-1} x + \sum_{x=1}^{n/2} x = \frac{(n/2-1)(n/2)}{2} + \frac{(n/2)(n/2+1)}{2} = \Theta(n^2).$$