我只是在尝试掌握主定理，在尝试计算t（n）=t（n/2）+n时有点困惑，使用主定理，答案是o（n）。
但只要看一下下面的代码：
fun(n)
{
if(n == 1)
return ;
for(int i=1;i<=n;i++)
{
printf("*");
}
fun(n/2);
}
上述代码的递归方程是t（n）＝t（n／2）+n，因此上述程序的时间复杂度必须为O（n）。
但如果从逻辑上考虑，程序运行的次数是：
n+n/2+n/4+n/8+=非登录。
因此，逻辑上，上述程序的时间复杂度必须是O（0）。
我现在很困惑。有人能帮我找出哪里错了吗？
最佳答案
不，序列值为2n。
n+n/2+n/4+n/8+=2n个
但是如果T（n）=2T（n/2）+n，那么它就是O（n logn）