Can you add time and space complexity?

[anukul-mohil]

learn/PalindromePartitionMinCut.java

Line 1 in 973773b

package questions.virendra;

Can you add time and space complexity for the exercise?

[RathoreGit]

Time complexity:: O(NlogN) -> we are iterating original array only 1 time(so complexity is O(N) ) and Searching for right index in temp array(i.e increasingSUB ) to replace our current value if our current value is less than the last element in temp array. so its complexity is (logN) so overall complexity is O(NlogN):

Space complexity:: O(N) -> We create a temp array i.e increasingSUB: for printing even we create a extra array parent i.e also of size N. still our complexity remain O(N).