pseudocode - theta 表示法中的最佳情况和最坏情况运行时间

Question

我不是在这里寻找答案，而是如何找到以下问题的最坏/最佳情况（以 theta 表示法）；for 循环通常是 (theta(n))，这将是最好和最坏的情况，但我认为这里发生了其他事情。任何帮助，将不胜感激。

Input: x (an integer), n (an integer)
addOnes(x, n) {
    if x > n then 
        for i <- 1 to n 
            return x + n
    else 
        for i <- x to n
                x <- x + n
    return x

编辑答案：

由于 return x + n 常数 (theta(1)) 将是最好的。

最佳 = (theta(1)) 最差 = (theta(n))

Answer 1

有两个分支，并且都可以到达。为了找到总体上最好和最坏情况的复杂性，找到每个循环的最好和最坏情况的复杂度，那么总体上最好的情况复杂度是两个分支的最好情况复杂度中更好的。对于最坏情况的复杂性类似。天真的问题中存在一个小问题，所以要保持警惕。