CODEWITHSUNDEEP
c++time-complexity
simsim
simsim

Reputation: 93

Time complexity of a recursive function when it does not have a specific rule for stopping

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 -> firstagain.

string findOriginalExp(string Exp){
    cout<<"*****findOriginalExp Function*****"<<endl;
    for(auto itr=graph.begin();itr!=graph.end();itr++){
        string s_tmp = itr->second;
        string f_tmp = itr->first;
        string nll = "null";

        if(s_tmp.compare(Exp) == 0){
            if(f_tmp.compare(nll) == 0){
                cout<< Exp <<" :is original experience.";
                return Exp;
             }else{
                return findOriginalExp(itr->first);
             }
        } 
    }
}

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

Upvotes: 0

Views: 78

Answers (2)

Jarod42
Jarod42

Reputation: 217283

Your code is equivalent to below code that I find more readable:

std::string findOriginalExp(std::string Exp)
{
    std::cout << "*****findOriginalExp Function*****" << std::endl;
    auto it = std::find_if(graph.begin(), graph.end(), [&](auto& p){ return p.second == Exp; });
    // assert(it != graph.end());
    if (it->first == "null") {
        std::cout << Exp << " :is original experience.";
        return Exp;
    }
    return findOriginalExp(it->first);
}

For complexity:

  • You copy Exp: O(M)
  • You do a linear search (with string) so O(NxM),
  • and a recursive call.

with

  • N: size of graph
  • M: max length of string.

Unless there is a infinite loop, the deepest recursive call count would be the size of graph (you basically have a tree and trying to find root, so longest would be a list)

Result would then be O(N²xM).

Upvotes: 0

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 122478

The thing is: Your function is not correct. Unless you have very particular preconditions on the contents of graph (which you didn't tell us) your code invokes undefined beahvior.

Maybe a compiler can convince you better than me. I added missing pieces to your code to get this:

#include <string>
#include <map>
#include <iostream>

using namespace std;

std::map<std::string,std::string> graph;

string findOriginalExp(string Exp){
    cout<<"*****findOriginalExp Function*****"<<endl;
    for(auto itr=graph.begin();itr!=graph.end();itr++){
        string s_tmp = itr->second;
        string f_tmp = itr->first;
        string nll = "null";

        if(s_tmp.compare(Exp) == 0){
            if(f_tmp.compare(nll) == 0){
                cout<< Exp <<" :is original experience.";
                return Exp;
             }else{
                return findOriginalExp(itr->first);
             }
        } 
    }
}

int main(int argc, char *argv[]){
}

And try to compile it with gcc -Werror yields the following error:

<source>: In function 'std::string findOriginalExp(std::string)':
<source>:25:1: error: control reaches end of non-void function [-Werror=return-type]
   25 | }
      | ^
cc1plus: all warnings being treated as errors
ASM generation compiler returned: 1
<source>: In function 'std::string findOriginalExp(std::string)':
<source>:25:1: error: control reaches end of non-void function [-Werror=return-type]
   25 | }
      | ^
cc1plus: all warnings being treated as errors
Execution build compiler returned: 1

Not returning something from a function that is declared to return something is undefined behavior. In the presence of undefined behavior your code may appear to work, but it is still broken.

It is not meaningful to discuss time complexity of that function (unless you include preconditions that assure no undefined behavior is actually encountered to the considerations).

Upvotes: 2

Related Questions