As Binary search algorithm is applied in each part, we have to take each array part sorted .
Total N elements are divided into Log N parts .
Each part contains elements in power of 2, and parts are like,
( 1 element ) ( 2 elements ) ( 4 elements ) ( 8 elements ) ( 16 elements ) ..........( 2^{log2n - 1 }elements ).
Hence, applying binary search algorithm in each of the parts starting from left to right,
Log (1) + Log (2) + Log (4) + Log (8) + log (16) + ................ + Log (2^{log2n - 1 )}
Log ( 1.2.4.8.16........(2^{log2n - 1}) )
Log ( 2^{0 }. 2^{1 }. 2^{2 }. 2^{3 }. 2^{4 }............. (2^{log2n - 1} ) )
Log ( 2 ^{(1 + 2 + 3 + 4 +............ +log2n - 1 ) })
O(Log ( 2 ^{(log2n - 1). (log2n) / 2 })) ==> O((Log_{2 }n - 1)(Log_{2 }n ) / 2) ==> O(Log_{2} n)^{2}