NikitosBandos's blog

Understanding Asymptotic Analysis of Algorithm
By NikitosBandos, history, 3 years ago, In Russian

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

O(n * sqrt(n) / 2), I dont have any proofs, but I've tested that program.

    int cnt = 0;
    int n;
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        for (int j = 2; j * j <= i; ++j) {
            ++cnt;
        }
    }
    cout << cnt << '\n';
    cout << (n * (int)sqrt(n)) / 2;

If n is equal 10000, output is:

651750
500000

So asymptotic of the algorithm is O(n * sqrt(n)).

Also if you will increase n, cnt would more than n * sqrt(n) / 2

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

    I am sure that asymptotic should be more accurate (the coefficient is not required, like 1/2).

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

      Can you proof it?

      I showed you, that if n >= 10000, asymptotic is equal O(n * sqrt(n))

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

nevermind

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

You can easily OEIS the sequence, it's simply a sum of floored square roots, and as one formula suggests it is equal to

Spoiler

I honestly have no clue how does this work but I hope it at least helps somehow!

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

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

→ Reply