我怎么才能算出这个递归算法的时间复杂度

Question

我想弄明白这道家庭作业的问题，但是我很困惑。我需要找到ClosestPair这个算法的时间复杂度，但是我不知道如何计算它会运行多少次。以下是目前为止的内容:

1. ClosestPair(S, p, r)
2.  if p == r 
3.      return ∞
4.  if r - p == 1
5.      return Distance(S[p], S[p+1])
6.  else
7.      m = floor ((p+r)/2) //m is the index of the median (the x-coordinate is the vertical dividing line)
8.      d1 = ClosestPair(S, p, m)
9.      d2 = ClosestPair(S, m+1, r)
10.     d = min(d1, d2)
11.     SPrime = points in S within distance d from S[m].x sorted by y.
12.     dPrime = BandClosestPair(Sprime, d)
13.     return min( dPrime, d)

这是我到目前为止的时间复杂度

1. 0
2. 1
3. 1
4. 1
5. 1
6. 1
7. 1
8. 
9.
10. 1 (It's not actually 1 but it will be a constant so it won't affect the algorithm's time complexity)
11. 
12.
13. 1

任何帮助都太棒了!我不想让你帮我做作业，只是想帮我解决一下。

Answer 1

这可能是您正在寻找的。https://en.wikipedia.org/wiki/Master_theorem

Tim Roughgarden在Coursera上也有一个关于这个话题的好讲座。https://www.coursera.org/learn/algorithm-design-analysis