Clever Geek Handbook

Computing the time complexity of functions when both contain each other?

Consider the following C code:

int foo(int x)
{
  if(x < 1) return 1;
  else return foo(x-1) + bar(x);
}

int bar(int x)
{
  if(x < 2) return 1;
  else return foo(x-1) + bar(x/2);
}

What will be the time and space complexity for each of the functions foo

and bar

?

+3


source to share


1 answer


The way to solve this problem is to look at what the functions are actually doing. There is no general rule. You just need to turn on your brain.

When you call foo (1000), how many calls to foo (999) will be made at least? How many calls will foo (998) be made at least?



...

How many calls to foo (501) will be made at least? How many calls to foo (500) will be made at least?

-2


source






More articles:


All Articles