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
Post a Comment