Time complexity of a function with while loop

Question

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?

• D.W.: cs.stackexchange.com/q/23593/755
• kiv: Yes, but I want to know if my intuition is correct?
• D.W.: I suggest following the systematic methodology there, then editing your question to show your work. That's how you can verify your intuition.
• Jörg W Mittag: 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.

Answer 1

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

• Steven: That equation cannot be true (although the sums is indeed in $O(N^2$).
• grus: @Steven I used - instead of + by mistake, I edited it and wrote it more precisely. Are there any other error here?

Answer 2

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