Big O notation for nested loops

Question

I am just learning the Big O notation and wanted to ask how it works for nested loops.

Is it true that in the case of

for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
       do something;
    }
}

It would be O(N squared), while

for (int i = 0; i < 1000; i++){
    for (int j = 0; j < N; j++){
        do something;
    }
}

It would be O(N) because the first loop has a constant? Or would it still be O(N squared)? Thank you

[How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) — hatchet - done with SOverflow, Mar 21 '18 at 18:11
Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation, as suggested when you created this account. [On topic](http://stackoverflow.com/help/on-topic) and [how to ask](http://stackoverflow.com/help/how-to-ask) apply here. Research before you post. — Prune, Mar 21 '18 at 18:14
Knowing this might help you with an answer on a test, but the reason you're learning it is so that you understand about the performance of algorithms. instead of "do something" try putting print("Number of loops = " + (i*j)); and running that. You'll see how your iterations grow as N grows. — Mark D, Mar 21 '18 at 18:16

score 4 · Answer 1 · edited Mar 21 '18 at 18:12

4

Your first statement is correct. N can be very large and O(n) takes it into account.

so first code is O(N^2) while second is O(1000*N) => still O(N)

BIG O notation does not include constants

edited Mar 21 '18 at 18:12

Henry

answered Mar 21 '18 at 18:12

Maciej

so would the "do something" bit ever affect the Big O? I realised that the we drop the constant in 1000N, hence the O(N). My "do something" is "if (j == a (which is args[0] int) && b[i] == a) then increase counter by 1. In which case would the "do something" change the Big O? Thanks for the answer btw. I will check as answered later – A.Bg Mar 21 '18 at 18:30
2

Your "doSomething" runs also in O(1), so the overall complexity remains O(N) in this example. – m.raynal Mar 21 '18 at 21:19

1 Answers1