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 ) ..........( 2log2n - 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 (2log2n - 1 )
Log ( 1.2.4.8.16........(2log2n - 1) )
Log ( 20 . 21 . 22 . 23 . 24 ............. (2log2n - 1 ) )
Log ( 2 (1 + 2 + 3 + 4 +............ +log2n - 1 ) )
O(Log ( 2 (log2n - 1). (log2n) / 2 )) ==> O((Log2 n - 1)(Log2 n ) / 2) ==> O(Log2 n)2