2

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

Mureinik
  • 297,002
  • 52
  • 306
  • 350
kingbol
  • 67
  • 6
  • [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

2 Answers2

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

Mureinik
  • 297,002
  • 52
  • 306
  • 350
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))

amanmehara
  • 134
  • 1
  • 8