Understanding Asymptotic Analysis of Algorithm

Revision ru1, by NikitosBandos, 2021-03-16 19:15:34

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!

Tags asymptotic

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian NikitosBandos 2021-03-16 19:15:34 510 Первая редакция (опубликовано)