시간복잡도에 관해서!

안녕하세요! 선생님 덕분에 많이 배우고 있습니다.

질문이 굉장히 많은데 모든 질문에 답변해주셔서 매우 놀라고 기뻤습니다..!

const solution = function (arr, m) {

  let cnt = 0;

  for (let lt = 0; lt < arr.length; lt++) {
    let sum = arr[lt],
      rt = lt;
    while (sum <= m) {
      cnt++;
      sum += arr[++rt];
    }
  }

  return cnt;

}

console.log(solution([1, 3, 1, 2, 3], 5)); // 10 
console.log(solution([1, 1, 1, 1], 5)); // 10
console.log(solution([10, 5, 2, 6], 100)); // 10

강의 듣기 전에 풀어본 것인데 혹시 반례가 있을까요?

그리고 제가 생각했을 때 이 코드의 반복문 실행 횟수가 가장 많아지는 경우는 입력된 수열이 [1, 1, 1, 1] 처럼 모든 요소를 다 더해도 m을 넘어가지 않는 경우에

 

for문의 lt가 0 일 때 :

while문 반복 실행 횟수 4

(sum = 1일때, 2일때, 3일때, 4일때)

 

lt가 1일 때:

while문 반복 횟수 3

(sum = 1, 2, 3)