CODEWITHSUNDEEP
algorithmtime-complexity
Deen John
Deen John

Reputation: 3750

What is the time complexity of these loops 1 and 2

I was going through an article on analysis of time complexity of loops at a very popular website(link given below) and according to that article the time complexity of below loops 1st and 2nd are O(1) and O(n) respectively. But i think the time complexity of both loop is same O(n) 

for (int i = 1; i <= c; i++) {  
    // some O(1) expressions
}

My reasoning : `c*n=O(n)

after going through answers below , My reasoning is wrong as there is no varying input n. the loop run is fixed- c times. hence irrespective of the input value n , the loop will run constant time. so O(1) complexity

for (int i = 1; i <= n; i += c) {  
    // some O(1) expressions
}

My reasoning : c*n=O(n)

Am i missing something ?I would be grateful if someone can help and explain

This is the link of the article : http://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/

Upvotes: 2

Views: 3893

Answers (4)

Codessci
Codessci

Reputation: 95

O(1) : The complexity of this loop is O(1) as it runs a constant amount of time c.

// Here c is a constant   
   for (int i = 1; i <= c; i++) {  
        // some O(1) expressions
   }

O(n): The complexity of the loop is O(n) if it is incremented or decremented by constant amount. For example, these loops have O(n) time complexity.

// Here c is a positive integer constant   
   for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

   for (int i = n; i > 0; i -= c) {
        // some O(1) expressions
   }

Upvotes: 0

YoungHobbit
YoungHobbit

Reputation: 13402

for (int i = 1; i <= c; i++) { // some O(1) expressions }

Here c is a constant. So basically, you are performing constant number of operation irrespective of the value of n. That is why is it considered as constant complexity, O(1).

for (int i = 1; i <= n; i += c) { // some O(1) expressions }

You are looping with a input value n, which is essentially variable with the given input to the program or algorithm. Now the c is again a constant, which will remain same for all the different values of n. The complexity is considered as O(n).

for (int i = 1; i <= n; i++) { // some O(1) expressions }

This is same as the above only, just that value of the c is 1.

All the complexities are represented in asymptotic notation format. Constant factors are removed because they will be same irrespective of the value of n.

Upvotes: 2

Haris
Haris

Reputation: 12272

1) There is no n in the picture, i dunno why you think it O(n). The loop is going from 1 to c, so its O(c), and as c is a constant, the complexity is O(1).

2) The loop starts from 1 and goes till n, incrementing c at every step. Clearly the complexity is O(n/c), which asymptotically is O(n).

Upvotes: 1

Sakib Ahammed
Sakib Ahammed

Reputation: 2480

A loop or recursion that runs a constant number of times is also considered as O(1).

Here: C is a constant value. So basically, you are performing constant number of operation irrespective of the value of n

   // Here c is a constant   
   for (int i = 1; i <= c; i++) {  
        // some O(1) expressions
   }

Also in Second Loop:

for (int i = 1; i <= n; i += c) {  
    // some O(1) expressions
}

Your reason c*n = O(n) is not correct. Here Increment by C. For n elements, loops occur n/c which is asymptotically O(n/c) ~ O(n)

Upvotes: 4

Related Questions