Search code examples
javarecursionruntimebig-ocomplexity-theory

Big O of functionF

static void functionF(int n) {
     for (int i = 0; i < n; i++) {
             functionF(n-1);
     }
}

I've calculated that:

if n = 2, the function gets called 4 more times. If n = 3, it gets called 15 more times. If n = 4, it gets called 64 more times. I am trying to work out a big O time complexity.

Solution

  • From a complexity pov, it takes factorial time to complete -> O(n!)

    Because every step, would run the amount of times specified in the last step. And note the diference between your function and:

    function alpha(n){
    for(int i = 0; i < n; n++){
        //Do some stuff
        alpha(i)
    }
}

    or

    function alpha(n){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            // Do some stuff
        }
    }
}

    The first one i can't really guess its time, buts lower than O(n!) The second one is the simple O(n²), which in any real situacion runs faster than O(n!)