The irony is that those languages are declarative, too, if we’re being pedantic. You’re not telling the computer what steps to follow, you’re telling the compiler what effects you want to have on the C/C++ abstract machine which is very much different from what the CPU will execute (mainly by the “as-if” rule).

C++ defines a program’s observable behavior as its interactions with volatile and library I/O functions, allowing any optimization that does not change those interactions (including their order). The compiler is thus free to rewrite your Bubble sort as a Merge sort if it were to somehow recognize that pattern, and for simple patterns (e.g. something that looks like a memcpy or memset) it often does. In fact there have been many security issues arising from the fact that the compiler has optimized away a memset that lacked an observable effect as defined by the standard, necessitating functions like explicit_bzero to get around that.

In any language, including C and C++, you need to have a model of execution to reason about time complexity. I grant that the model is generally simpler for procedural languages, especially given how the transformations usually don’t affect more than constant-factor operations, but you can apply largely the same to functional languages by reasoning about unavoidable work.

e.g. to sum all the elements in a list, every element must be visited and therefore the operation is O(N). To retrieve an item from a :gb_sets, you have to traverse a binary-tree structure and therefore the operation is O(log N). And so on.

Elixir is also simpler than other functional programming languages in that it’s based on Erlang, which defines every function everywhere as side-effecting because of tracing, which precludes all optimizations that would be visible when tracing is enabled (e.g. you cannot remove a function call that provably does “nothing,” because it would disappear from the trace), so @lud is quite right in that you can “reason procedurally” about time complexity in Elixir.

With SQL, it is mostly about having the right indexes. You can see what the database does by running it with explain, analyse, etc selected. You can paste the results into sites like this to get a "better” view. Edit: a resource on SQL indexes

In Elixir, I tend to think in terms of data structures and the most efficient way to transform/run an algorithm over them. There is an efficiency guide for Erlang.

The Erlang run-time system exposes several trace points that allow users to be notified when they are triggered. Trace points are things such as function calls, message sending and receiving, garbage collection, and process scheduling.

The compiler respects all trace points that it has control over, and as such cannot perform even the simplest of optimizations that would affect tracing, like removing a redundant function call, unused parameters, ignored return values, and so on^[1].

1. Technically we could try to maintain the illusion when tracing is enabled for the specific function that was opitimized away, but the maintainability trade-off is the epitome of “not worth it.” It’s far more involved than it first appears. ↩︎

I’m not sure, it seems to me that lambda calculus has infinite CPU speed and infinite memory, but I’m not really sure what you are looking for besides the traditional big O.

But I hope someone else, more versed into those kind of things, will chime in

Thanks for the insight. I will read the guide.