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](https://stackoverflow.com/q/11032015). [Big O, how do you calculate/approximate it?](https://stackoverflow.com/q/3255) — Bernhard Barker, Feb 25 '18 at 08:22

score 4 · Answer 1 · answered Feb 25 '18 at 07:59

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 '18 at 07:59

Mureinik

297,002
52
306
350

amanmehara · Accepted Answer · 2018-02-25T08:17:17.767

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))

Complexity after Arrays.sort and for loop

2 Answers2