What is the time complexity of these dependent nested loops?

 

This question already has an answer here:

  • Big O, how do you calculate/approximate it? 22 answers 
    • first part of the question ,  
i = 0, 1, 2, 3, 4, ... , n   
j = i = 0, 1, 2, 3, 4, ... n  

first time: i = 0  
inner loop will execute from 0 to n ( n times ) 

second time , i = 1  
j = 1, 2, 3, 4, .... , n ( n-1 times)  

third time : i = 2  
j = 2, 3, 4, ... , n

i = 0 : j = 0 -> n (n)  
i = 1 : j = 1 -> n (n-1)   
i = 2 : j = 2 -> n (n-2)   
i = n - 1 (i < n) : j = (n - 1) -> n ( 1)    

sum( 1 + 2 + 3 + 4 + ..... + n) = n*(n + 1)/2 = O(n^2)    
second part of the question m does not increment this loop will not  
stop.
    链接地址: http://www.djcxy.com/p/39354.html

    上一篇: 如何在O（n）时间或O（nlogn）运行一个算法？

    下一篇: 这些相关嵌套循环的时间复杂度是多少？