Please read the new rule regarding the restriction on the use of AI tools. ×

Problem in determining time complexity

Revision en1, by jha_gaurav98, 2018-07-29 06:34:36

What will be the time complexity of the following nested loop:

for(int i=2;i<n;++i){
    for(int j=i;j<n;j+=i){
        //some code here
    }
}

Actually I was participating in a competition on Codechef last night. And there was a question for which I thought of a solution like this. But the range of n was [2, 106] and time limit was 1.5s. So I thought that my solution will exceed the time limit and hence I didn't submit it. But after the contest I saw another guy submitting the same solution and getting his solution accepted. So, can someone tell what is the exact time complexity of this code snippet?

Link for question

Thanks in advance

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English jha_gaurav98 2018-07-29 06:34:36 787 Initial revision (published)