0
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ depends on how the sampling of i is done. It might be the case that the while loop doesn't break out $\endgroup$
    – Rinkesh P
    Oct 29, 2022 at 8:18
  • $\begingroup$ 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? $\endgroup$
    – gnasher729
    Oct 29, 2022 at 22:00

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.