시간복잡도에 관해서!

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

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

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)

lt가 2일 때:
while문 반복 횟수 2
(sum = 1, 2)
 
lt가 3일 때:
while문 반복 횟수 1
(sum = 1)
 
이렇게 되니까
입력된 수열의 길이가 n이라 하면
최악에 경우에 실행 횟수는 n + n - 1 + n - 2 + ... + 1
 n + n - 1 + n - 2 + ... + 1 (lt = 0일떄 while실행횟수 ~ 마지막) 
1 + 2 + 3 + ... + n (lt = arr.length-1일때 while ~ 처음)
-------------------------
n * (n + 1)
 
이니까 총 실행 횟수는 (n^2 + n) / 2 여기서 최고차항 뺴고 다 없애고 계수도 없애면 n^2이니까 시간복잡도는 O(n^2) 이라고 생각했는데 제가 시간복잡도를 맞게 구한걸까요? 
 
반면에 선생님의 코드는 가장 반복 횟수가 많아지는 경우가
제가 고민해봤을 떄 입력된 수열의 길이가 n일때, n -1 번째까지는 다 더해도 m을 안 넘는데 마지막꺼 더했을 때 m을 넘어가는 경우일 것 같은데.. 잘 모르겠어요. 이 경우가 맞을까요? 
그럼 이 경우는 for문의 rt가 0에서 마지막 요소까지 쭉 가다가 (실행횟수 = 요소의 갯수 = n번)
마지막 요소에서 와일문이 rt = 0부터 마지막 요소까지 실행되니까
총 2n번 실행되는게 최대 반복 횟수일거같은데 
제가 생각한 것이 맞는지 궁금합니다.
그리고 선생님처럼 이렇게 푸는 방법은 솔직히 제 머리론 죽었다 꺠어나도 못떠올릴거같은데 문제를 많이 풀다보면 머리가 좋아질까요..?

인프런 커뮤니티 질문&답변