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.
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).
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).
What if here p is a large value.Does the code still works in log(n) times?
Ofcourse, it will. Run your code on different values of n and p and analyse the number of calls made each time.
You can define a
countervariable 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.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))$$$.
This example is an open problem By always giving them worst cases (continue calling $$$inv(x - 1)$$$ in some magic cases) then below function have $$$O(x)$$$ complexity in some cases, but actually it run pretty fast and I think it is about $$$O(log\ n)$$$
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))