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