How do I calculate the time complexity of the following function?

Question

Here is a recursive function. Which traverses a map of strings(multimap<string, string> graph). Checks the itr -> second (s_tmp) if the s_tmp is equal to the desired string(Exp), prints it (itr -> first) and the function is executed for that itr -> first again.

string findOriginalExp(string Exp){
    cout<<"*****findOriginalExp Function*****"<<endl;
    string str;
    if(graph.empty()){
        str ="map is empty";
    }else{
        for(auto itr=graph.begin();itr!=graph.end();itr++){
        string s_tmp = itr->second;
        string f_tmp = itr->first;
        string nll = "null";
        //s_tmp.compare(Exp) == 0
        if(s_tmp == Exp){
            if(f_tmp.compare(nll) == 0){
            cout<< Exp <<" :is original experience.";
            return Exp;
            }else{
                return findOriginalExp(itr->first);

            }
        }else{
            str="No element is equal to Exp.";
        }
     }

    }
    return str;
    }

There are no rules for stopping and it seems to be completely random. How is the time complexity of this function calculated?

Answer 1

I am not going to analyse your function but instead try to answer in a more general way. It seems like you are looking for an simple expression such as O(n) or O(n^2) for the complexity for your function. However, not always complexity is that simple to estimate.

In your case it strongly depends on what are the contents of graph and what the user passes as parameter.

As an analogy consider this function:

int foo(int x){
    if (x == 0) return x;
    if (x == 42) return foo(42);        
    if (x > 0) return foo(x-1);            
    return foo(x/2);
}

In the worst case it never returns to the caller. If we ignore x >= 42 then worst case complexity is O(n). This alone isn't that useful as information for the user. What I really need to know as user is:

• Don't ever call it with x >= 42.
• O(1) if x==0
• O(x) if x>0
• O(ln(x)) if x < 0

Now try to make similar considerations for your function. The easy case is when Exp is not in graph, in that case there is no recursion. I am almost sure that for the "right" input your function can be made to never return. Find out what cases those are and document them. In between you have cases that return after a finite number of steps. If you have no clue at all how to get your hands on them analytically you can always setup a benchmark and measure. Measuring the runtime for input sizes 10,50, 100,1000.. should be sufficient to distinguish between linear, quadratic and logarithmic dependence.

PS: Just a tip: Don't forget what the code is actually supposed to do and what time complexity is needed to solve that problem (often it is easier to discuss that in an abstract way rather than diving too deep into code). In the silly example above the whole function can be replaced by its equivalent int foo(int){ return 0; } which obviously has constant complexity and does not need to be any more complex than that.