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?

  • $\begingroup$ cs.stackexchange.com/q/23593/755 $\endgroup$
    – D.W.
    Apr 10 at 6:25
  • $\begingroup$ Yes, but I want to know if my intuition is correct? $\endgroup$
    – kiv
    Apr 10 at 6:28
  • $\begingroup$ I suggest following the systematic methodology there, then editing your question to show your work. That's how you can verify your intuition. $\endgroup$
    – D.W.
    Apr 10 at 6:30
  • 2
    $\begingroup$ 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. $\endgroup$ 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)$

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.