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

Answer 1

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).