CODEWITHSUNDEEP
recursionbig-otime-complexity
Lawrence Wong
Lawrence Wong

Reputation: 1139

Time complexity (in big-O notation) of the following recursive code?

What is the Big-O time complexity ( O ) of the following recursive code?

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;
}

My answer is O(n log(n)). Is it correct?

Upvotes: 0

Views: 601

Answers (1)

Makoto
Makoto

Reputation: 106430

Where I'm sitting...I think the runtime is O(n log n). Here's why.

  • You are making n calls to the function. The function definitely depends on n for the number of times the following two operations are made:

    • You loop up to 2*log(n) values to increment a sum.

For a worst case, n is extremely large, but the overall runtime doesn't change. A best case would be that n <= 2, such that only one operation is done (the looping would not occur).

Upvotes: 2

Related Questions