Determining Time Complexity of a Recursive Function Calling From inside a Loop

Question

I am not sure, is that question previously asked in SO or not. Well, I was checking frequency of a char in an array. I am pretty weak in determining complexity, so I thought this community can help me to get the point! I am very much sorry, if I posting it with some abstraction! If anyone can help me it will be great!

Here, is my code:

class SearchAChar{
private static int getOccurance(char [] a, char k, int l, int r, int count){
    if(l == r) return count;

    if(a[l] == k){a[l]='0';count++;}

    return getOccurance(a, k, l+1, r, count);   
}
public static void main(String [] args){
    char [] arr = {'a', 'e', 'b', 'c', 'b', 'c', 'd','a'};

    for(int i=0; i<arr.length; i++){
        if(arr[i] == '0') continue;
        System.out.println("Occurance of : " +arr[i] + " is "+ getOccurance(arr, arr[i], i, arr.length, 0) +" times!");
    }
}
}

what should be the run-time complexity of this problems??

note that with a Map, you can make this O(n) instead of O(n²) — Kepotx
– Kepotx, Commented Feb 21, 2019 at 10:59

Pyrozen · Accepted Answer · 2019-02-21 10:41:57Z

3

Since there is a for-loop and inside for-loop there is a recursive function which has run-time complexity of O(n), that makes worst time complexity is O(n^2) where n is the length of array of char.

answered Feb 21, 2019 at 10:41

Pyrozen

311 silver badge6 bronze badges

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

Comments

Laksitha Ranasingha · Accepted Answer · 2019-02-21 12:52:19Z

1

Let's try to decompose; I am talking about the worst case scenario complexity.

n = length of the array

for(int i=0; i<arr.length; i++){} - this does not loop over n times because you update the array by setting seen char to 0 in the recursive function. And if the char is 0 you continue. So it's like O(n/2).
getOccurance(a, k, l+1, r, count) - is recurse over each character until the length is == incrementer. The best way to represent recursive function call stack is as a tree. For example, this image shows how the call stack is being built calculating fibonacci.

But your getOccurance function doesn't invoke itself twice like in above fibonacci function picture. So we could say it has invocations like in one branch of the tree. In other words, here we see the call stack sequence is like 0,1,2... n-1, Therefore, we could calculate the complexity O(n).

If we put those two steps together we get. O(n/2 * n)

But also as @Coderino mentioned - Non dominant terms are not considered in worst case performance.

In conclusion, the complexity of above code is O(n^2).

Some useful resources - https://users.cs.duke.edu/~ola/ap/recurrence.html

Complexity of recursive factorial program

edited Feb 21, 2019 at 12:52

answered Feb 21, 2019 at 11:34

Laksitha Ranasingha

4,6171 gold badge32 silver badges36 bronze badges

9 Comments

Coderino Javarino Over a year ago

The getOccurance can be easily rewritten into a linear loop; no way this is even remotely O(2^n)

Laksitha Ranasingha Over a year ago

@CoderinoJavarino You may be rewrite it, but this is not a linear loop, can you please elaborate how?

Coderino Javarino Over a year ago

Recursion and loops have same capabilities, and each can be rewritten as an equivalent of the other with the same complexity. This one is trivially a local count var, and a simple for (i = l; i <=r; i++) loop that increments it conditionally depending on a[i]

Laksitha Ranasingha Over a year ago

@CoderinoJavarino you are giving a general statement. How does that relate to the OP's code in the question? Of course, it's conditional for the loop but not for the recursive call. That's why I said the loop is not `O(n).

Papai from BEKOAIL Over a year ago

@LaksithaRanasingha thank you so much for giving time and well detailed explanation! :)

|

Collectives™ on Stack Overflow

Determining Time Complexity of a Recursive Function Calling From inside a Loop

2 Answers 2

Comments

9 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

9 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related