Is this an example of logarithmic time complexity?

Question

It is commonly said that an algorithm with a logarithmic time complexity O(log n) is one where doubling the inputs does not necessarily double the amount of work that is required. And often times, search algorithms are given as an example of algorithms with logarithmic complexity.

With this in mind, let’s say I have an function that takes an array of strings as the first argument, as well as an individual string as the second argument, and returns the index of the string within the array:

function getArrayItemIndex(array, str) {
  let i = 0
  for(let item of array) {
    if(item === str) {
      return i
    }
    i++
  }
}

And lets say that this function is called as follows:

getArrayItemIndex(['John', 'Jack', 'James', 'Jason'], 'Jack')

In this instance, the function will not end up stepping through the entire array before it returns the index of 1. And similarly, if we were to double the items in the array so that it ends up being called as follows:

getArrayItemIndex(
  [
    'John', 
    'Jack', 
    'James', 
    'Jason',
    'Jerome',
    'Jameson',
    'Jamar',
    'Jabar'
  ], 
  'John'
)

...then doubling the items in the array would not have necessarily caused the running time of the function to double, seeing that it would have broken out of the loop and returned after the very first iteration. Because of this, is it then accurate to say that the getArrayItemIndex function has a logarithmic time complexity?

Answer 1

Not quite. What you have here is Linear Search. Its worst-ccase performance is Theta(n) since it has to check all the elements if the search target isn't in the list. What you have discovered is that its best-case performance is Theta(1) since the algorithm only has to run a few checks if you get lucky.

Binary search on pre-sorted arrays is an example of an O(log n) worst-case algorithm (the best case is still O(1)). It works like this:

Check the middle element. If it matches, return. Otherwise, if the element is too big, perform binary search on the first half of the array. If it's too big, perform binary search on the second half. Continue until you find the target or you run out of new elements to check.

In Binary Search, we never look at all the elements. That is the difference.