UGC-NET | UGC-NET CS 2017年11月–III |问题33

考虑递归关系：

其中b和c是常数。 与上述递推关系对应的算法顺序为： （A） N （B） N ^2. （C） n日志n （D） N ^3. 答复: （D） 说明： 我们可以使用主定理来解决这个递归关系：

T(n) = aT(n/2) + Θ(nklogpn)
In given question:
T(n) = 8T(n/2) + Cn
here a = 8 and b = 2 and k = 1.
 clearly a > bk 
So T(n) = Θ(nlogba )
T(n) = Θ(nlog2 8)
ie T(n) = Θ(n3)

因此，选项（D）是正确的。 这个问题的小测验