big o - Big-O if inner for loop starts with a number => 1 -


i trying understand whether the big-o notation changes if inner loop not start @ 0, rather 1, 2, 3 or more.

e.g. change inner loop starts @ 3 or big-o still n squared?

for(int = 0; < n; i++)     for(int j = 3; j < n; j++) 

and while @ it, might ask whether make difference if or j incremented 3 in each iteration. help!

for big o explanation, see what plain english explanation of "big o" notation?

concerning specific question:

case 1

for(int = 0; < n; i++)     for(int j = 0; j < n; j++) 

has complexity

  • o(n2) because doing n·n operations
  • o(n2)

case 2

for(int = 0; < n; i++)     for(int j = 3; j < n; j++) 

has complexity

  • o(n2 - 3n) because doing n·(n - 3) operations
  • o(n2)

case 3

for(int = 0; < n; i++)     for(int j = 0; j < n; j*=3) 

has complexity

  • o(n2/3) because doing n·(n/3) operations
  • o(n2)

Comments