arr.sort((a, b) => a - b).map(num => num ** 2);

What would be a Big O of the following operation?

As I understand Big O of imbedded sort function in JS is O(Nlog(N)) and Big O of map is O(N), therefore Big O is O(Nlog(N))?

CodePudding user response：

The complexity of your function f, for arr of size n. We'll assume:

arr.sort ∈ O(nlogn)
arr.map ∈ O(n),

We can just sum these terms, since these operations are done serially (one after the other. Thus,

f(n) ∈ O(nlogn   n)

Note that the nlogn term will grow slowly, but eventually:

as n -> infinity, nlogn >> n
thus, as n -> infinity, nlogn   n -> nlogn

So we can simplify to just O(nlogn) for sufficiently large n.

All of this is to say, yep, you got it.