performance - 确定算法的运行时间

我一直在试图确定以下算法的渐近运行时间。
alg-1和alg-2算法都以n个条目作为输入并生成一个数组。
Alg-1将是

ALG-1(A[1,...,n])
1: B= ALG-1(A[1,...,⎿n/2⏌])
2: C= ALG-2(A[⎿n/2⏌+1,...,n])
3: return ALG-2(B,C)

考虑到ALG-2的运行时间f（n）是Θ（√n），我想确定ALG-1的渐近运行时间。
我试图建立算法的递归，然后通过主定理来解决它，但我甚至不知道如何开始。如果有人能帮我一把，我会很高兴的。

最佳答案

让T_k表示在输入sizeALG-1时运行n = 2^k所需的时间我假设您的ALG-2(B, C)意味着ALG-2在B和C的连接上运行，这是长度n的。看来你又复发了

T_k = T_{k - 1} + sqrt(n / 2) + sqrt(n) = T_{k - 1} + C * sqrt(2^k),

其中C是常数。如果你不断地用T_{k - 1}来扩展它，你会得到

T_k = C * sqrt(2^k) + C * sqrt(2^{k - 1}) + C * sqrt(2^{k - 2}) + ...

这是一个几何级数，所以和的阶数与前导项的阶数相同（基本上，第一项和所有剩余项的和差不多大）。所以T_{k - 2}的顺序是T_k或sqrt(2^k)。