Time complexity of sorted square

Question

0.00/5 (No votes)

See more:

New to algorithms and would apprecaite if someone could please let me know if my solution is O(nlogn) time or O(n^2)?
Ive seen better solutions but was just curious what this implementation is for time complexity.

function sortedSquaredArray(array) {

  const sArr = [...array];
    const result = sArr.map((num)=> {
        return Math.pow(num, 2);
    });
    return result.sort((a,b)=> a - b);  
}

What I have tried:

learning big o but not 100% if im right.

Posted 25-Oct-21 19:28pm

ecma Script

Updated 25-Oct-21 21:21pm

Add a Solution

3 solutions

Solution 2

'Probably' (see, for instance javascript - What is Array.prototype.sort() time complexity? - Stack Overflow[^]) it is O( n log n).
Anyway, you could make a test to establish it experimentally.

Posted 25-Oct-21 20:13pm

CPallini

Comments

OriginalGriff 26-Oct-21 2:43am

Mozilla disagrees:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
"The time and space complexity of the sort cannot be guaranteed as it depends on the implementation."

CPallini 26-Oct-21 3:31am

Well, I know that, however I'm quite confident (that's the reason for'probably') that no implementation would choose O(n^2) while O(n log n) is available.

ecma Script 26-Oct-21 15:14pm

thank you for this @cpallni and originalgriff

Solution 3

thank you both. In regards to first post the context is.

take in non empty array of integers and return an orderd array of intergers ascending order order eg [-5,10,1] will return [1,25,100]]

length not specified

Posted 25-Oct-21 21:21pm

ecma Script

Comments

OriginalGriff 26-Oct-21 4:04am

Don't post this as an answer - it means that only you get notified it has been posted rather than the people you want to speak to.
To talk directly to a member, use the "Comment" or "Reply" facility below their post.

But it's irrelevant what the context is: the browser implementation of the Javascript sort is internal: it'#s not defined to use any particular algorithm, so it's time complexity is not defined or known (or fixed: it could change with a new browser version). Even if it currently is n log n today, it could be better or worse tomorrow, and you might never know. It's not a good idea to rely on undocumented features: if you need a specific complexity, you have to write your own code.

And your "sorted order" example is ... um ... not valid. :D

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Accepted Answer · 2021-10-25T20:05:00

We can't tell you - it would depend entirely on the sorting function, and we have no idea how that is implemented. It is not required to use any particular algorithm, and the time complexity of sorting algorithms varies considerably.

If you want a specific complexity, you would need to code your own sort function.