Блог пользователя Night_Lord

Автор Night_Lord, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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.

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

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))