Night_Lord's blog

How to calculate complexity from recursion?
By Night_Lord, history, 3 years ago, In English

Hello,I know this question might be silly to most of you but I desparetly seeking the answer.Here is my question-

#include <bits/stdc++.h>

using namespace std;

long long BaseConversion(long long n,long long p)
{
    if(n<p)return n;
    return n%p + 10*BaseConversion(n/p,p);
}

int main() {
    long long n;
    while(cin>>n)
    {
    	cout<<BaseConversion(n,9)<<endl;
    }
    return 0;
}

How do I calculate complexity from this problem?As long as I know about complexity depends on loop. But in recursion how can I calculate this? The above code works in 0<=N<=10^18 range .How this code gives log(n) complexity?

Thanks.

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

For this example, just print the values the recursion is taking and observe what is happening. In general, think about how many branches the recursion takes and use that to analyze the complexity. If it splits into the same amount of cases each time, as it often does, you can probably use the master theorem (google it).

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Although, there are better ways to analyse time complexity of recursion, but in this case, you can see the number 'n' is divided by 'p' every time the function is called, therefore, it is called roughly log(n)[base p] times before reaching base case. Hence, the time complexity is O(logn).

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What if here p is a large value.Does the code still works in log(n) times?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ofcourse, it will. Run your code on different values of n and p and analyse the number of calls made each time.

      → Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

You can define a counter variable and increase it by 1 at every call of the function, run your code on multiple tests to see how many times your function is called.

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it

There is no general way to calculate good complexity. However by always giving the function worst cases it can deal with then you can get such highest upper bound of the complexity. (But dont try to give it run infinity or testcases like zero-divisions).

And yes, there is some functions where you can get very-worst-theory-complexity if you continue pushing it worst case to handle, but it isnt false to say it is $$$O(f(x))$$$ complexity, when actually it run in $$$O(g(x))$$$ that $$$O(g(x)) < O(f(x))$$$.

Example

However, it some simple recursive function or some dnc-recursive with simple implementation or whatever function you can get its recursive formula. Then you can use this helpful [Master Theorem](https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms))

→ Reply