Can anyone tell me the methods to change the time complexity from O(N^2) to O(N) or O(NlogN).
Suggestions are most welcome.
Firstly you should understand the theory behind time complexity and what big O notation denotes. In short we describe time complexity as the number of operations our program performs. This can be a decently accurate measurement of program’s runtime as we know that we can perform 4 \cdot 10^8 operations per second.
Moving to the big O notation, it denotes the theoretical maximum our program will perform. Thus, O(N) performs about N operations, meaning inputs up to 4 \cdot 10^8 will run in about 1 second. Similarly O(N log N) allows for inputs up to 10^6-10^7 to run in about 1 second. The story is similar for other units…
So what do we conclude? There’s no global way to reduce time complexity of a solution which can be applied to any algorithm. You need to find a specific way to do so.
For example, running two loops inside each other, both of which perform N operations produces O(N^2) runtime. To reduce it to O(N log N) you could use a map to remove one of the loops or sort the input beforehand… But can you do these to improve the runtime complexity will highly depand on the problem you’re solving.
This should give you a general idea of how to reduce the complexity, but if you want more specific approach you should give us the problem you are solving as well as your current solution. 
great explanation
1 Like