判断代码时间复杂度是否为Big Theta(n²)的技术咨询

public int calculateValue(int i, int j) {
    int count = 0;
    for(int r = 0; r < i; r++){
        for(int c = 0; c < j; c++){
            if(A[r][c] == 1){
                count++;
            }
        }
    }
    return count;
}

要确定一段代码的时间复杂度是Θ(n²)，必须同时满足O(n²)（上界）和Ω(n²)（下界）。你已经确认它属于O(n²)，核心就是判断是否满足Ω(n²)，这里有个直白的判断逻辑：

Ω(n²)的定义是：存在常数c>0和足够大的n，使得代码的运行时间至少为c*n²。结合这段代码，关键看嵌套循环的总迭代次数——因为循环内的判断、计数都是O(1)操作，总执行步骤数完全由循环次数决定。

分两种核心情况分析：

• 当i和j均为Ω(n)时：比如i=n、j=n，或者i=0.6n、j=0.7n（只要i≥c₁n，j≥c₂n，c₁、c₂是大于0的常数），此时循环总次数i*j的量级就是n²，既满足O(n²)也满足Ω(n²)，代码时间复杂度就是Θ(n²)。
• 当i或j的量级小于n时：比如i固定为5、j=n，或者i=√n、j=n，此时循环总次数是O(n)或O(n^1.5)，达不到n²的下界，就不满足Ω(n²)，自然也不是Θ(n²)。

简单来说，判断步骤就是：

1. 确认循环总迭代次数i*j的量级
2. 只要i和j都和n同量级（不会比n小太多），那就是Θ(n²)；否则不是。

内容的提问来源于stack exchange，提问作者Enzo Zuanazi Bestetti