Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
470 views
in Technique[技术] by (71.8m points)

time complexity - Big-O of fixed loops

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

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

Please log in or register to answer this question.

Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...