stevensonmt
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
Where Next?
Trending in Questions
Hello!
Suppose you are building workflow (order / task / payment) processing system with the following requirements:
Each workflow con...
New
I’m aware of 2 such projects, are there others?
git: GitHub - team-alembic/realworld: A fullstack Phoenix LiveView application with back...
New
I having some trouble figuring out if I have set myself too strict of standards for my production server. Currently I can handle 75% of r...
New
Hi everyone.
My team and I have been working on a fairly modest app based around video streaming and chat, but we’ve landed a customer t...
New
I really like the adapter patterns that ecto, nebulex, waffle, etc. use and would love find something similar for a key management servic...
New
Hello folks!
So at work, we are seeing some situations where we have to define some “fixed” strings that are used across the codebase in...
New
How Can I Optimise Compile Time Dependencies
I have been building an elixir application for about 2 years now. Many modules and files ha...
New
Other Trending Topics
I fully migrated to my own harness from Anthropic/Gemini and I think it’s time to share it. Welcome DSH, the DeepSeek Harness, fully writ...
New
Hey. Is there anyone here who creates agents in their apps? Not talking about using agents, but creating them. I’m finding it pretty diff...
New
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
New
There has been a thread to discuss the Stack Overflow Developer Survey on this forum every year since 2018, so here’s yet another one for...
New
I love Elixir. It’s one of 2 programming languages I’ve ever fallen in love with.
But I don’t use it anymore.
Serverless was the promis...
New
Emily is an Elixir library that runs Nx computations on Apple’s MLX. Install it as the default Nx backend and Nx, defn, Axon, Nx.Serving,...
New
Latest on Elixir Forum
Sponsor Spotlight
Bringing learning, work and compliance together since 1987.
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #library
- #deployment
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #elixirconf
- #channels
- #exunit
- #discussion
- #code-sync
- #podcasts
- #javascript
- #onsite
- #dialyzer
- #docker
- #authentication
- #ai
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #blog-post
- #elixirconf-us
- #elixir-ls
- #phoenix_html
- #iex
- #graphql
- #genstage
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #elixirconf-eu
- #api
- #forms
- #security
- #hex
Our Sponsors
Build Elixir applications with speed and confidence.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Error tracking, logs, uptime, and Just Enough APM. Built for developers.
Elixir, Erlang & BEAM conferences from Code Sync - join us in 2026!
Master modern tools, write cleaner code, and tackle real-world challenges.
Producing high quality Elixir screencasts since 2017.
The deployment platform built for Elixir: PaaS ease, VPS control.
The team behind Membrane, Popcorn, LiveDebugger. Available for hire.
Courses that'll move you from confusion to "Aha, now I get it!"
Showing Posts 1 to 2- Show Best Posts
- Show All (oldest first)
- Show All (newest first)
tj0
It really depends on what the inputs to the function l_i_s are. It looks like the envelopes consist of fixed size elements from a quick glance.
So then I would estimate it as:
So when we’re adding big-O notation, 1 + 3 just end up being 2*O(n) which is just O(n). The complexity would be dominated by the sort O(n log n) or l_i_s (might be O(n) or O(n^2)).
Regarding time complexity and performance, you would also have to assign some sort of time to each of the function calls and know roughly the max elements of the envelope vs the elements fed to l_i_s. For instance, it could be an O(n^2) for microsecond calls vs O(n) for millisecond calls. Or it could be the sort is the most expensive. Tough to really say from just looking at the code without an idea of the data being fed into it.
stevensonmt
Thanks for the insight.
The input is a fixed list of lists of integer pairs, given as [[width, height]].
l_i_s/3I think is worst case O(n*mlogm) where m is the combined length of sublists with equal first values (widths). I’m not sure if m can equal n and I’m assuming theEnum.findislogn.