Data Structures

The Iteration Method for Calculating Recursion (functions) Complexity

So as I'm starting over on Data Structures, today I learned about the iteration method as a tool to calculate recursion's complexity. Basicly, this method says that in order to calculate the worst case complexity, we need to understand how the recursion advance.

Let's say we got a recursive Sum function, like so:

public static int sumFunc(int[] intArr) {
    int x = 0;
    return recSumFunc(intArr, x, 0);
}

private static int recSumFunc(int[] intArr, int sum, int i){
    sum += intArr[i];
    return (++i == intArray.length()) ? sum : recSumFunc(intArr, sum, i);
}

Within each recursion (or, iteration of the function), we reduce the total the amount of numbers we need to iterate over by 1, until we get the sum of all of the number within the array. Since we're only reducing it by one, and in our case (a sum function) we have to pass on all of the numbers, the worst case (and actually, also best case) complexity is O(n).

With other recursions, like Binary Search, we're reducing are "future checks needed" by half on each iteration. Therefore, worst complexity for Binary Search is O(logn).

Hope this gave you some intuition, or refreshed your memory, on how to understand the complexity of recursions by the iterative method.

RwK