Technically linear! On Mon, Nov 26, 2012 at 9:47 PM, 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) (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. > > > > --