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