CODEWITHSUNDEEP
calgorithmsortingtime-complexitybig-o
Tommaso Pellegrini
Tommaso Pellegrini

Reputation: 55

Recursive functions complexity containing another function (Big O notation)

I've seen many similar questions but not quite what I'm looking for. I'm supposed to find the complexity for the code below. What makes this code different from what I've seen here already is that the function I have to find the complexity contains another function with a given complexity.

I think I can solve this but can't give the correct answer. Any detailed explanation would be very nice, also to help me better understand the flow of finding the complexity in those kinds of functions. The code is in C.

 void f(int v[], int n, int i, int j){
    int a = v[i]; 
    int b = v[j]; 
    int m = (i+j)/2;
    g(v,n);
    if(i<j){
        if(a<b) f(v,n,i,m);
        else f(v,n,m,j)
    }
    return; 
}

The f function is called in the main where v is an array: f(v, n, 0, n-1). The g function complexity is O(n).

Now, I really can't decide between O(log n) or O(n log n). Seeing that we're dividing the workspace in half using the int m I know it's logarithmic, but does the G function adds up and turn everything into O(n log n)?

Thank you.

PS: if an answer like this has been asked already, I couldn't find it and redirection would be great in case anyone else stumbles on the same problem as mine.

Upvotes: 1

Views: 124

Answers (1)

tucuxi
tucuxi

Reputation: 17945

Your f function will execute exactly log(n) times (the range between i and j is always halved); each of these times, it will execute g, with an additional cost of O(n). Therefore, the total complexity is O(n * log(n)), which is the total number of times the inner loop* of g is called.

(* I am assuming that there is an inner loop in g for explanation purposes, because that is what you find in many, but certainly not all, O(n) functions).

Upvotes: 1

Related Questions