java - 我对代码段的运行时分析是否正确？

Question

这类似于这个问题runtime analysis of the following recursive method

我正在尝试分析这段代码

为了分析这一点，我看到外层循环将执行 n/c 次。然后每次外循环运行时，内循环也会执行 n/c 次。因此，如果您放弃常量，该段总共将运行 n^2/c^2 或 O(n^2)。

是否也有一种视觉方式可以做到这一点，类似于(来自 http://courses.cs.washington.edu/courses/cse373/15wi/lectures/lecture3.pdf)幻灯片 19？我尝试这样做但得到了 (c *(n)(n + 1))/2 我不确定是否正确。

Answer 1

(c *(n)(n + 1))/2

= c*(n^2 + n)/2

= (c/2)*(n^2 + n)

去掉常量并保持 n 的最高次幂给出 O(n^2) 的最终答案