pseudocode - シータ表記での最良の場合と最悪の場合の実行時間

Question

ここで答えを探しているわけではありませんが、次の問題の最悪/最良のケースを見つける方法 (シータ表記) です。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

回答を編集:

x + n が返されるため、定数 (theta(1)) が最適です。

最良 = (シータ(1)) 最悪 = (シータ(n))

Answer 1

2 つのブランチがあり、両方にアクセスできます。全体の最良ケースと最悪ケースの複雑さを見つけるには、各ループの最良ケースと最悪ケースの複雑さを見つけます。次に、2 つの分岐の最良ケースの複雑さのうち、全体の最良ケースの複雑さがより優れています。最悪の場合の複雑さについても同様です。そして、初心者がつまずくように問題に組み込まれている小さな落とし穴があるので、注意してください。