Link to home
Start Free TrialLog in
Avatar of Simon Leung
Simon Leung

asked on

Find worst case time complexity of function

Is my calculation of the following function correct or not ?  Thx

T= 4+ 2(n+1) + n/2
  = 4+ 2n+2 +log(n)
  = 2n +log (n) + 6
  ≥ 2log(n) + log(n) +6
  ≥ 3log(n) + 6
  ≥ log(n)+2

So the time complexity is O(log n).




function Search(array, item) {

   let minIndex = 0;
   let maxIndex = array.length
   let currentIndex;
   let currentElement;                

   while (minIndex <= maxIndex) {      
      currentIndex = Math.floor((minIndex + maxIndex) / 2);
      currentElement = array[currentIndex];

      if (currentElement < item) {
         minIndex = currentIndex + 1;
      }
      else if (currentElement > item) {
         maxIndex = currentIndex - 1;
      }
      else {
         return currentIndex;
      }
   }
}
Avatar of David Johnson, CD
David Johnson, CD
Flag of Canada image

That is to be expected from a binary search
https://en.wikipedia.org/wiki/Binary_search_algorithm
ASKER CERTIFIED SOLUTION
Avatar of Bernard Savonet
Bernard Savonet
Flag of France image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial