Time complexity of the given function with constant loop and recursion

Question

What would be the time complexity for this, will it be O(logn)?

fun(int n) {
    if (n < 2)
        return 1;
    int counter = 0;
    for (int i = 1; i <= 8; i++)
        fun(n / 2);
    for (int i = 1; i <= Math.pow(n, 3); i++)
        counter++;
}

Why would it be log n? You've got a for-loop up to n-cubed in the function. — khelwood
– khelwood, Commented Jul 19, 2020 at 20:35
What does fun return? int or void? Anyway it doesn't compile. — user4910279
– user4910279, Commented Jul 19, 2020 at 23:11

amit · Accepted Answer · 2020-07-20 04:15:22Z

8

The complexity of the function is:

T(n) = n^3 + 8*T(n/2)

n^3 comes from the last loop, which is going from 1 to n^3
8*T(n/2) from calling fun(n/2) 8 times (in the first loop)

To find the complexity, one can use master theorem with: a = 8, b = 2, f(n) = n^3

Using case 2:

log_2(8) = 3, and indeed f(n) is in Theta(n^3), giving this function complexity of O(n^3*logn).

edited Jul 20, 2020 at 4:15

answered Jul 19, 2020 at 20:44

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user4910279 Over a year ago

The variable counter is not used, so optimizer may remove the last loop.

Collectives™ on Stack Overflow

Time complexity of the given function with constant loop and recursion

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related