-1

How to calculate time and space complexity for these algorithms? I referred many sites but its confusing me. please any one explain me.

1.

 for(i=0;i<n;i++)
 {
    for(j=i;j<n;j++)//this for loop is based on previous 'i'
    {
       foo();
    }
 }

2.

while(m<n)
{
    for(i=0;i<n;i++)
    {
         foo();
    }
}

If possible explain me with some more example. Thanks.

user2864740
  • 60,010
  • 15
  • 145
  • 220
user3496195
  • 139
  • 1
  • 2
  • 11
  • What *are* the bounds? Provide an answer, and justification of such. This will show work on your part, and allow answers to bolster or correct any such claims. (This is also a duplicate.) – user2864740 Aug 10 '14 at 02:28
  • 1
    Try running these loop manually and observe how many computations will happen in the worst case. case 2 appears to be an open candidate for thinking about worst case as there is not much given about m other than the condition m – gmfreak Aug 10 '14 at 03:18
  • 1
    The snippet 2 does not run at all or is an infinite loop (unless `foo` changes m or n). – Henry Aug 10 '14 at 07:55

1 Answers1

4
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.