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
