Anyway, to the point. I was doing the Tie Ropes challenge. It took many tries simply because I was reading too fast and I was trying to solve it the pythonic way. The challenge was looking for O(n) complexity.
My problem is that my best pythonic solution was rated at O(n**2):
def solution(K, A): start = 0 end = 1 count = 0 while end <= len(A): while end <= len(A) and sum(A[start:end]) < K: end += 1 if sum(A[start:end]) >= K: count += 1 start = end end += 1 return count
To me it looks like O(n) complexity since the loop(s) iterate with end of the slice, and regardless of which loop you are in it increments the end element. (Apologies to those unfamiliar with a Python slice. Practically all other languages you'd need a "start" and "length" instead.)
What says you on this snippet? O(n) or O(n**2)? Explain please.