Good Day, everybody!
A few days earlier i faced up with a problem in which was asked to define an asymptotic of the algorithm below:
int cnt = 0, n;
cin >> n;
for (int i = 2; i <= n; i++) {
for (int j = 2; j*j <= i; j++) {
if (n % j == 0) cnt++;
}
}
cout << cnt << endl;
My version is O(n*sqrt(n)) is not the right answer. Maybe someone can explain me what is the right answer and why? Thnx in advance!
O(n * sqrt(n) / 2), I dont have any proofs, but I've tested that program.
If n is equal 10000, output is:
So asymptotic of the algorithm is O(n * sqrt(n)).
Also if you will increase n, cnt would more than n * sqrt(n) / 2
I am sure that asymptotic should be more accurate (the coefficient is not required, like
1/2).Can you proof it?
I showed you, that if n >= 10000, asymptotic is equal O(n * sqrt(n))
nevermind
You can easily OEIS the sequence, it's simply a sum of floored square roots, and as one formula suggests it is equal to
I honestly have no clue how does this work but I hope it at least helps somehow!
The easiest way to calculate complexity of such function is to use integrals. Here you have \begin{gather*} \sum\limits_{i=1}^n \sqrt{i} \end{gather*}
You can look at it as an approximation for this integral with step 1: \begin{gather*} \sum\limits_{i=1}^n \sqrt{i} \approx \int_0^n\sqrt x dx = \frac{2}{3}x^{\frac{3}{2}}\Big|_0^n = O(n\sqrt n) \end{gather*}
If you want to actually prove it, you can notice that the function $$$\sqrt x$$$ is increasing, so you can calculate lower bound by approximating area under function on a segment $$$[x; x+1]$$$ with $$$f(x) \cdot 1$$$ and upper bound by approximating with $$$f(x+1) \cdot 1$$$ and then work with these inequalities
P.S. You created a blog saying it's russian (look at a flag, there was some setting), so it's not visible to users with english interface