oh, understood, i thought it takes constant time ....suppose if it takes, then is there any benefit of this recursion compared to reverse(str) = str[lastcharacter] + reverse(str(0, last-1))
it will reduce the recursion depth right ? No gain on time complexity though a small correction, btw, T(n) = 2*T(n/2) + cn On Tue, Nov 27, 2012 at 12:48 PM, atul anand <[email protected]>wrote: > considering '+' , here will take Cn time . Here '+' is for concatenate , > now this concatenation taking place in constant time?? , i dont think > so..internally it will be adding elements to new m/m space and for that it > need to traverse each character...so it will take cn time. > so T(n) =T(n/2) + cn = nlogn > > On Tue, Nov 27, 2012 at 11:17 AM, shady <[email protected]> wrote: > >> what is the time complexity of this? >> >> str_reverse(str){ >> if(isempty(str)) return str; >> else if(length(str) = even) then split str into str_1 and str_2; (of >> equal length) >> return str_reverse(str_2)+str_reverse(str_1); >> else split str into str_1, str_2, str_3; //if str is odd length, e.g. >> len = 7, split by 1-3 | 4 | 5-7 >> return str_reverse(str_3)+str_2+str_reverse(str_1); >> } >> >> -- >> >> >> > > -- > > > --
