For recursive code , we find time complexity by writing the recurrence relation first and then using Master Theorem or Recursion tree approach to find the complexity..
For the recurrence equation :
T(n) = a T(n / b) + f(n)
a denotes the number of recursive subproblems , 'n/b' being the size of each problem and f(n) being the time taken in the non recursive part of the entire code..
Here in the given code we are calling function 8 times indirectly by using the while loop..
Hence a = 8 here ..Also b = 2 as we have used "search(n/2)" as recursive call..
Now for f(n) , we have to calculate complexity of non recursive part which is the nested for loop in the given code that follows recursive calls..
Hence coming to for loop :
i runs n2 times and for each value of 'i' , 'j' runs log2n due to the increment step j = j * 2..
Hence total times 'j' runs including all values of 'i' = O(n2 logn)
Thus f(n) can be taken as O(n2logn)
Thus the recurrence relation for the entire code is written as :
T(n) = 8T(n/2) + O(n2 logn)
Now here nlogba = n3 here which is polynomial times greater than n2 logn..
Thus T(n) = O(n3) for the given code which is the required complexity..