Time complexity of the given function with constant loop and recursion

user_7160038 0
Viewed 432

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++;
}
big-o time-complexity algorithm java
1 Answers

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

user_5726700
Related