Another efficient approach

#1

hi…i think in worst case…its complexity is o(nnlog(n))…
i saw similar question on some another platform…and submitted same solution…but got TLE in that…please help me to get more efficient approach…(i m not able to understand its editorial as well)

#2

Hey @Gurankit_Pal_Singh
The complexity is actually nlogn only
T(n) = 2*T(n/2) + N
So if you solve this equation you will get T(N) as nlogn

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

hii…i’m sorry…i forgot to respond…but if time coplexity is o(nlogn) then why am i getting tle in that question???..its constraints are 10^5…so worst case will be 2*10^6…and despite given 2 seconds it is not passing

#5

https://ide.codingblocks.com/s/238285 here’s link to my code

#6

@Gurankit_Pal_Singh
Please re-open this doubt so that someone can be assigned to it else it’ll be difficult to track and respond to this doubt
Thanks

#7

@Gurankit_Pal_Singh
You’re using push_back to create half strings
That is causing issue
to get half string use s.substr(0,s.length()/2) and s.substr(s.length(),s.length()/2)

#8

thanks sir to resolve my doubt

1 Like