Time complexity of linear search in a loop?-CodePudding

 For I=1 to n
     For J=1 to n 
         k = b[I]
         F = Linear_search(a,k)
         Print F
      J=J*2

What will be the time complexity of above algorithm? I thought it would be O(nlogn) but there is a linear search too in algorithm which has complexity O(n).So what will be the complexity O(nlogn) or O(n) or will it be O(n^2 logn)?

CodePudding user response：

There are :

n iterations for the first loop
log(n) iterations for the second

The program will call Linear_search nlog(n) times.

The complexity of the linear search being O(n), the complexity of the program will then be O(n^2log(n))