CODEWITHSUNDEEP
algorithmtime-complexity
swr
swr

Reputation: 11

confused about the time complexity of the follwing func. A good explanation would be helpful

If the the first loop runs for n+1 times. second loop runs for n(n+1) times. third loop will run for ??? it has n^2+1 one relation with with with the second loop i guess but how about with the first one 

somefunction(n) {  
 c = 0      
 for (i = 1 to n*n)          
   for (j = 1 to n)               
     for (k = 1 to 2*j)                    
        c = c+1     
  return c 
}

Upvotes: 0

Views: 41

Answers (1)

chepner
chepner

Reputation: 531165

The first loop has O(n**2) iterations.

The second loop has O(n) iterations.

The third loop has O(n) iterations as well, since j is steadily increasing towards n.

(It's a little easier to see if you sum up the number of times c = c + 1 executes for the two inner loops combined. The inner loop runs 2 times for j = 1, 4 for j = 2, ..., and 2*n times for j = n. 2 + 4 + .. + 2*n = O(n**2).)

You can then (loosely speaking) multiply the three values together to get a total bound of O(n**4).

Upvotes: 2

Related Questions