Hitting the degenerate case depends on the function you're computing in question. It's quite possible that the tasks will complete in the given order. I think you're giving too much credit to Erlang's task scheduler.
Also I'm not sure how one would even implement a tail recursive map function on a singly linked list. The cons operation can only add elements to the front of the list. I looked up how the map operation is implemented in Erlang. It isn't tail recursive:
https://github.com/erlang/otp/blob/172e812c491680fbb175f56f7...
I'm interested to know how you'd implement a tail-recursive version of map (continuations aren't allowed).
I'm not saying the task scheduler is perfect, but I'd be really, really weirded out if it gave priority to the final process spawned, and worked its way backwards, which would be necessary for the degenerate case (that is, we spawned off items 1,2,3,4 in that order, but they completed 4,3,2,1. I would expect them to finish in close to 1,2,3,4 order, which would leave it at O(1) on each receive).
I'd implement a tail recursive map as -
map(F, L) -> map(F, L, []).
map(_, [], Acc) -> lists:reverse(Acc);
map(F, [H|T], Acc) -> map(F, T, [F(H) | Acc]).
The only O(n) operations are, yes, a completely degenerate case of when messages get sent back (which is -incredibly- unlikely; with Erlang's task scheduling you're likely only going to ever have a max message queue length of a few items, so it's more likely a constant factor. To get the degenerate case you would need it to finish in -reverse- list order, that is, would need to finish with the last one first, then the next to last one, etc), and when reversing the list(s) built up from the map at the end (as under the covers I'm pretty sure map is written to be tail recursive), which while technically O(n), is still incredibly fast.