0

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?

Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83
coder101
  • 840
  • 2
  • 11
  • 29

3 Answers3

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

vib
  • 2,254
  • 2
  • 18
  • 36
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 .

Community
  • 1
  • 1
Namit Sinha
  • 1,415
  • 3
  • 16
  • 30
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.

gnasher729
  • 51,477
  • 5
  • 75
  • 98