Technically linear!
On Mon, Nov 26, 2012 at 9:47 PM, 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) (Calculate mid =O(1), then extract(0,mid) ,
> extract(mid+1,end)
> return str_reverse(str_2)+str_reverse(str_1); Reversals again
> have linear dependence on length.
> 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);
}
Similar argument for the odd length stuff. So the net complexity is in fact
linear.
>
>
>
>
--
