time complexity - Big-O of fixed loops

Question

I was discussing some code during an interview and don't think I did a good job articulating one of my blocks of code.

I know (high-level) we are taught two for loops == O(n^2), but what happens when you make some assertions as part of the work that limit the work done to a constant amount.

The code I came up with was something like

String[] someVal = new String[]{'a','b','c','d'} ;// this was really - some other computation
if(someVal != 4) {
  return false;
}

for(int i=0; i < someVal; i++){
  String subString = someVal[i];
  if(subString.length() != 8){
    return false;
  }
  for(int j = 0; j < subString.length(); j++){
    // do some other stuff
  }
}

So there are two for loops, but the number of iterations become fixed because of the length check before proceeding.

for(int i=0; i < **4**; i++){
  String subString = someVal[i];
  if(subString.length() != 8){ return false }

  for(int j = 0; j < **8**; j++){
    // do some other stuff
  }
}

I tried to argue this made it constant, but didn't do a great job. Was I completely wrong or off-base?

question from:https://stackoverflow.com/questions/65647231/big-o-of-fixed-loops

Answer 1

Your early exit condition inside of the for loop is if(subString.length() != 8), so your second for loop is executed any time if the length exactly 8. This in fact makes the complexity of the second for loop constant, as it is not depending on the input size. But before your first for loop you have another early exit condition if(someVal != 4) making the first for loop also constant.

So yes, I would follow your argumentation, that the complete function has a constant big-O time complexity. Maybe repeating in the explanation that big-O always describes an upper bound complexity, which will never be crossed and constant time factors can be reduced to 1.

But keep in mind, that a constant complexity based on real world input could still be longer in execution time than a O(n) complexity, based on the size of n. If it would be a known pre-condition that n does not grow beyond a (low) given number, I would not argue about the Big-O complexity, but about overall expected runtime, where the second constant for loop could have a larger impact than expected by Big-O complexity analysis.