 # Help with Time Complexity of a Problem

Hello Again! I was solving a Problem today , Link

and i quickly wrote a brute force / naive solution with a horrible complexity (i thought that before )

I was caluclating divisors of number and that too in a recursive function, I seriously didn’t expect it to get accepted. But since it did, now i’m wondering what is the time complexity of my solution. Can someone tell me what’s the time complexity or how come is this fast enough to pass all tests.

My Solution (C++ Code):

#include <bits/stdc++.h>
using namespace std;

vector<int> divisors(int n){
vector<int> res;
for(int i=1;i*i<=n;i++){
int one=i;
if(n%one==0){
res.pb(one);
if(one!=n/one)
res.pb(n/one);
}
}
sort(res.begin(),res.end());
return res;
}

vector<int> solve(int n){
if(n==1){
vi res;
res.push_back(1);
return res;
}

vector<int> temp = divisors(n);

pair<int,int> checker = {0,0};

for(int i=0;i<temp.size()-1;i++){

vector<int> _t = divisors(temp[i]);

if(_t.size()>=checker.first){
checker.first=_t.size();
checker.second=temp[i];
}

}

vector<int> res;
res.push_back(checker.S);

vector<int> next = solve(checker.S);

for(int i = 0 ; i< next.sz ; i++){
res.push_back(next[i]);
}

return res;
}

int32_t main(){

ios_base::sync_with_stdio(false);cin.tie(0);

int n;
cin >> n;
vector<int> temp = solve(n);
temp.push_back(n);
set<int,greater<int>> ans(temp.begin(), temp.end());

for(int x:ans){
cout << x << ' ';
}

return 0;
}


Since the sort function in divisors is the bottleneck, I counted the total number of comparisons made for each n \in [1, 1000000] and plotted a graph. Here’s what it looks like.

Looks like a mix of log and \sqrt[x]{} to me. 2 Likes