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

Question

I am trying to understand whether the the big-o notation changes if the inner loop does not start at 0, but rather 1, 2, 3 or more.

E.g. does it change anything that this inner for loop starts at 3 or is the big-o still n squared?

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

And while I am at it, I might as well ask whether it would make a difference if the i or the j were incremented by 3 in each iteration. Thanks for your help!

Answer 1

For a big O explanation, see What is a plain English explanation of "Big O" notation?

Concerning your specific question:

Case 1

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

has complexity

• o(n²) because you are doing n·n operations
• O(n²)

Case 2

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

has complexity

• o(n² - 3n) because you are doing n·(n - 3) operations
• O(n²)

Case 3

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

has complexity

• o(n²/3) because you are doing n·(n/3) operations
• O(n²)

Answer 2

Neither aspects change the time complexity. Big-O notation only cares about the order of growth, it does not care about work reduction by a constant amount or factor.

Answer 3

It doesn't change anything. All of these measurements are behavioral trends, and Big-O is the asymptotic upper bound. Individual iterations or offsets are meaningless when the sample size is "arbitrarily large," which is what you're interested in.

What you're really looking for is the fastest growing term (the things that you add), without any coefficients. So, there's no difference between n^5 and (n-3)^5, because the fastest growing term of the latter is...n^5.