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

Categories

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

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

Please log in or register to answer this question.

Welcome to ShenZhenJia Knowledge Sharing Community for programmer and developer-Open, Learning and Share

548k questions

547k answers

4 comments

86.3k users

...