Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Problem in determining time complexity

Правка en1, от 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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский jha_gaurav98 2018-07-29 06:34:36 787 Initial revision (published)