algorithm - 求解Ω和Θ(O，Omega和Theta表示法)

Question

我已经解出了一个运行时间为（2^n）的指数递推关系
时间。
我如何找到Ω和O的相同递推关系。
我想如果是Θ（2^n），也应该是O（2^n），对吗？
如何找到Ω，下界？
我试图解决重复关系：
t（n）=2t（n-1）+c。

Answer 1

如果是作业，你可以尝试把它画成递归树，其中节点代表函数调用所需要的操作的复杂性。
编辑：关于下限，欧米茄定义为下限。如果你有θ（确切的行为），你也有Omicron和Omega只是不太精确。
所以

Theta(n) <=> O(n) AND Omega(n)

扰流器
如果我没记错的话，这就是你的解释。。。
你有一棵树，在它的根上，你只有C（为解决方案添加边距的工作），你必须在两个分支中吐痰（同样是以C作为工作），节点被分支n次

     C
    /|
   C C
  /| |\
 C C C C
/| ......

完全解决方案
因为树的深度为n，底部的2^n节点都具有C的复杂性，那么你的复杂度n-1 > C, 2C, 4C....(2(n-1)*C)级别，它们应该归纳为2^n*c
因此，最终的复杂性应该是2*(2^n)*C，即theta(2^n)