Complexity after Arrays.sort and for loop

Question

In java, if I sort using Arrays.sort() (n log n) and then use a for loop o(n) in the code, what will be the new complexity ? is it n^2 log n or n log n

How to find time complexity of an algorithm. Big O, how do you calculate/approximate it? — Bernhard Barker
– Bernhard Barker, Commented Feb 25, 2018 at 8:22

amanmehara · Accepted Answer · 2018-02-25 08:17:17Z

4

Answer: O(nLog(n))

non nested complexities can be simply added. i.e. O(n) + O(nLog(n))

For large n, nLog(n) is significantly greater than n. Therefore, O(nLog(n)) is the answer.

Read this: https://en.wikipedia.org/wiki/Big_O_notation

Note:

if the complexities are nested then the complexities are multiplied, for example:

Inside a loop of order n, you are doing a sort of order nLog(n).

Then complexity will be O(n * nLog(n)). i.e. O(n²Log(n))

edited Feb 25, 2018 at 8:17

answered Feb 25, 2018 at 8:12

amanmehara

1341 silver badge8 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Mureinik · Accepted Answer · 2018-02-25 07:59:53Z

4

If you perform the for loop after, you have an O(nlog(n)) operation followed by an O(n) one. Since O(n) is negligible compared to O(nlog(n)), your overall complexity would be O(nlog(n)).

answered Feb 25, 2018 at 7:59

Mureinik

316k54 gold badges402 silver badges406 bronze badges

Collectives™ on Stack Overflow

Complexity after Arrays.sort and for loop

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related