if it is constant i.e T(n)=2*T(n/2) + O(1) = O(n)
so simple non-recursive approach is better...
On Tue, Nov 27, 2012 at 1:29 PM, shady <sinv...@gmail.com> wrote:
> 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 <atul.87fri...@gmail.com>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 <sinv...@gmail.com> 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);
>>> }
>>>
>>> --
>>>
>>>
>>>
>>
>> --
>>
>>
>>
>
> --
>
>
>
--
