# What is the expected time complexity of this algorithm?

In the following algorithm $$A[1..n]$$ denotes an array $$A$$ of size $$n$$, of $$n$$ distinct integers. Func1() and Func2() are functions that run in $$\mathcal O(\log n)$$ and $$\mathcal O(n)$$ time, respectively.

Foo(A[1..n])
if n == 1:
return

while (True) {
Func1()
i = random[1, 2, ..., n] \\ uniform random sampling from {1, 2, ..., n}
if (A[i] is in the middle third of A[1..n]):
break
}
Func2()
Foo(A[1..i])
Foo(A[i+1..n])


Without the loop I can get easily $$T(n) = \mathcal O(n) + \frac{1}{n}\sum^{n}_{i=1}(T(i) + T(n-i))$$, but I'm not sure what to do with the loop. Would $$T(n) = \frac{2}{3}\log n + \frac{1}{3}\times \left(\mathcal O(n)+\frac{3}{n} \sum^{2n/3}_{i=n/3}(T(i) + T(n-i))\right)$$ be correct?

• depends on how the sampling of i is done. It might be the case that the while loop doesn't break out Commented Oct 29, 2022 at 8:18
• If n = 2, can A[I] be in the middle third of A[1..2]? Or is I = 1 in the first third, I = 2 in the last third, and nothing in the middle third at all? Commented Oct 29, 2022 at 22:00