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))?
Javascript Array: what is a Big O of performing sort and then map right after on it?
Viewed 415
1 Answers
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.
Related