I’m trying to come to grips with Big O notation and time complexity analysis. I think the following algorithm is O(n*n). Can someone confirm:

  def max_envelopes(envelopes) do
    envelopes
    |> Enum.map(&(List.to_tuple(&1)))
    |> Enum.sort_by(&{elem(&1, 0), -1 * elem(&1, 1)}) # sorts by first item ascending order then second item descending b/c second item mult by -1
    |> Enum.map(&elem(&1, 1)) # since widths are sorted only need longest increasing subpath for heights
    |> l_i_s(0, Map.new())
  end
  
  def l_i_s([], ndx, dp), do: ndx
  def l_i_s([h | hts], 0, %{}), do: l_i_s(hts, 1, %{0 => h})
  def l_i_s([h | hts], i, dp) do
    if dp[i - 1] < h do
      # in this case the current height h is greater than the last used ht and can be appended
      l_i_s(hts, i + 1, Map.put(dp, i, h))
    else
      # in this case the current height h is less than the last used ht and we must backtrack to the
      # last used ht that is greater than h
      replace =
        0..i
        |> Enum.find(fn ndx -> dp[ndx] >= h end)

      dp = %{dp | replace => h}
      # b/c we did a replace rather than append the length of the series (tracked by i) does not change for recursive call
      l_i_s(hts, i, dp)
    end
  end