1

When we write powering a number as a divide and conquer algorithm in theoretical computer science the runtime would be T(n) = 2T(n/2) + Θ(1) in my opinion, yet according to my teacher's slides it is T(n) = T(n/2) + Θ(1). Why that? I added the 2 because the algorithm gets split into 2 subproblems? Am I wrong? Slide of the prof

4

1 回答 1

1

在每一步中,问题都被分成两个相同的小部分。由于它们是相同的,因此无需对它们中的每一个进行计算。因此不需要乘数2

于 2017-08-23T14:16:55.743 回答