Skip to main content
2 of 2
added 171 characters in body; edited title
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

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?

kiv
  • 339
  • 2
  • 8