runtime - I'm in a middle of a computer science class, learning time complexity and stuck on a problem (Java)

Question

So, first, here's the code: code from our presentation

We are learning time complexity, and according to our teacher, the run time for this one is n^2 +4n . But for me and my friends, it seems like this is wrong. It's a for loop, inside a for loop, inside a for loop, so doesn't this needs to be n^3? What I need is some explanation on what is the runtime for this code, we literally sat for an hour with the teacher on this (the teacher is not that smart, because she didn't really learned this subject she just had a couple of classes about it) and all she could say was that you don't count the first for loop. Please any explanation?

question from:https://stackoverflow.com/questions/65869966/im-in-a-middle-of-a-computer-science-class-learning-time-complexity-and-stuck

Answer 1

There are several points to make here:

1. Having three nested loops doesn't imply O(n^3) complexity. It depends on the loops and what happens within the loops. It could be anything between O(1) and never halting.

2. Your teacher should specify what should be measured more precisely: the number of steps for the entire piece of code? Or just the two inner loops, ignoring the outer loop?

3. You need to specify what the variable parameters are. In this case it's pretty clear what it is (probably n, and not i or j), but it helps to be precise.

4. The code doesn't run because there is a syntax error: b[i] ) reader.nextInt();. So strictly speaking, there is no time complexity to reason about here.

5. OK, now assuming that the line should actually read b[i] = reader.nextInt();, the variable parameter is n, and the whole code should be measured: your teacher is right that the entire code runs in O(n^2), because the outer and the second loops share the same index variable i. So the outer loop iterates exactly once.

6. It doesn't really make sense to be much more precise than O(n^2) unless you define precisely what counts as 1. So stating something that looks precise like n^2 +4n is pretty much meaningless without much more context.