recursion - 次の再帰コードの時間計算量 (big-O 表記) は?

Question

次の再帰コードの Big-O時間計算量 ( ) は?O

public static int abc(int n) {
    if (n <= 2) {
        return n;
    }
    int sum = 0;
    for (int j = 1; j < n; j *= 2) {
        sum += j;
    }
    for (int k = n; k > 1; k /= 2) {
        sum += k;
    }
    return abc(n - 1) + sum;
}

私の答えはO(n log(n))です。それが正しいか？

Answer 1

私が座っている場所...ランタイムはO(n log n)だと思います。理由は次のとおりです。

• 関数をn回呼び出しています。この関数は、次の 2 つの操作が行われる回数をnに依存します。

  • 合計をインクリメントするには、最大 2*log(n) の値をループします。

最悪の場合、nは非常に大きくなりますが、全体の実行時間は変わりません。最良のケースは、n <= 2 であり、1 つの操作のみが実行されます (ループは発生しません)。