title: Why is the time complexity O(n^2) rather than O(n^3)?
body: <p>I solved <a href="https://leetcode.com/problems/3sum/description/" rel="nofollow noreferrer">a problem on LeetCode</a>, and I found <a href="https://discuss.leetcode.com/topic/22619/python-easy-to-understand-solution-o-n-n-time/27" rel="nofollow noreferrer">an answer</a> of which time complexity is O(n^2), why? Here is the code</p>
  
  <pre><code>class Solution(object):
      def threeSum(self, nums):
          """
          :type nums: List[int]
          :rtype: List[List[int]]
          """
          result = []
          nums.sort()
          for i in xrange(len(nums)-2):
              if i &gt; 0 and nums[i] == nums[i-1]:
                  continue
              l, r = i + 1, len(nums) - 1
              while l &lt; r:
                  if nums[l] + nums[r] == -nums[i]:
                      result.append([nums[i], nums[l], nums[r]])
                      l, r = l + 1, r - 1
                      while l &lt; r and nums[l] == nums[l-1]:
                          l += 1
                      while l &lt; r and nums[r] == nums[r+1]:
                          r -= 1
                  elif nums[l] + nums[r] &gt; -nums[i]:
                      r -= 1
                  else:
                      l += 1
          return result
  </code></pre>