loopstime-complexitynested-loopslinear-search

Time complexity of linear search in a loop?


 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)?


Solution

  • There are :

    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))