Time complexity of nested for loops

Question

the following sample loops have O(n^2) time complexity Can anyone explain me why it is O(n^2)? As it depends on the value of c...

loop 1---

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

loop 2---

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

If c=0 ; then it runs infinite number of times , in the similar way if c value is increased then the number of times the inner loops run will be decreased

Can anyone explain it to me?

should it be i -=c in the second loop ?

vib
– vib

2015-06-11 13:52:44 +00:00
Commented Jun 11, 2015 at 13:52 — vib
– vib, Commented Jun 11, 2015 at 13:52
Yea sorry it is i=i-c

coder101
– coder101

2015-06-11 13:55:45 +00:00
Commented Jun 11, 2015 at 13:55 — coder101
– coder101, Commented Jun 11, 2015 at 13:55

vib · Accepted Answer · 2015-06-11 13:46:40Z

1

Each of these parts of code takes a time O(n^2/c^2). c is probably considered a strictly positive constant here and therefore O(n^2/c^2) = O(n^2). But it all depends on the context...

answered Jun 11, 2015 at 13:46

vib

2,2742 gold badges20 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Othman Benchekroun Over a year ago

Read the second loop again !

Community · Accepted Answer · 2017-05-23 11:51:15Z

1

Big-O notation is a relative representation of the complexity of an algorithm.

Big-O does not says anything about how many iterations your algorithm will make in any case .

It says in worst case your algorithm will be making n squared computations. Which is useful if you have to compare 2 algorithms.

In your code if we assume c to be a constant then it could be ignored from Big-O notation because Big-O is all about comparison and how thing scale. where constants play no role.

But when c is not a constant the correct Big-O notation would be O(n^2/c^2).

Read this awesome explanation of Big-O by cletus .

edited May 23, 2017 at 11:51

CommunityBot

11 silver badge

answered Jun 11, 2015 at 14:02

Namit Sinha

1,4553 gold badges17 silver badges31 bronze badges

Comments

gnasher729 · Accepted Answer · 2015-06-11 13:49:29Z

0

For every FIXED c, the time is O (n^2). The number of iterations is roughly max (n^2 / c^2, n^2) unless c = 0. n^2 / c^2 is O (n^2) for every fixed n.

If you had code where c was changed during the loop, you might get a different answer.

answered Jun 11, 2015 at 13:49

gnasher729

53k5 gold badges83 silver badges106 bronze badges

Collectives™ on Stack Overflow

Time complexity of nested for loops

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related