使用 Big-O 渐近分析计算总 运行 时间

Question

int f1(int n)
{ 
    int sum = 73; 
    for (int i=0; i < n; i++)
    { 
        for (int j=i; j >= 5; j/2)
        {
            sum--;
        }
    }
}

我正在计算此算法的总 运行 时间，以确定每条语句的成本。 我到目前为止是这样的：

for(int i=0; i < n; i++) // runs in n time
for(int j=i; j >= 5; j/2) // runs in T(n/2) time
sum-- // runs nc/2 times (because it lies in inner loop which is running n/2 times)

现在，我必须找到 T(n) 但我不知道是要执行此 n*T(n/2)) 还是 n+ T(n/2) . 当 T(n/2) 通过它给出的替换求解时，O(log n) 将是该算法 O(n^2) 或 O(n log n)?

Answer 1

我认为 Big-O 将是 O(n*Log2(n))

for(int i = 0; i < n; ++i) // n
    for(int j = i; j >= 5; j /= 2) //log2(n) Because j is divided by 2 each step
        sum--; // 1