Why is Time Complexity halved in Solution1 of Challenge 4 Ch2 in Data Structures for Python coding interview course. I would think the time complexity is n(n-1) == n^2. I don’t understand why it is being multiplied by 1/2, or n(n-1)/2. Can someone please explain. Thanks in advance.
That’s because while there are indeed 2 nested loops, the inner one is not really iterating over the entire list, only the items to the right of the current index. The accumulated result of the items to the left of the current index is stored to be reused in the next iteration which on average saves you half the work in that iteration of the inner loop.