Time and Space complexity calculations for Algorithms

Linear Search

size_t Algo_linear_search(int *input_list, size_t input_size, int search_item) {
  for (int i = 0; i < input_size; i++) {
    if (input_list[i] == search_item) {
      return i;
    }
  }
  return -1;
}

This is the simplest case, you just check every element in the list to find the element you need, in the worst-case scenario, the element you need is the element you checked last, in which case, n iterations would have passed, so the time complexity is $O(n)$

Space complexity is $O(1)$

Binary Search

NOTE: this assumes that the provided input_list has already been sorted

• we first calculate the middle element in the input_list with the following formula: $\text{mid}=\text{left}+\frac{\text{right}-\text{left}}{2}$
• Then we check if this middle value is the search item
• if yes then hoorahh!
• On the other hand, if this is not equal to the item we are searching for, then we check if the item is bigger or smaller than this value
• If the element is (hypothetically)bigger and since the input_list is sorted (assuming in accending order) then we have proved that the element lies in the right half.
• So we can just discard the left half altogether and just focus on the right half.

We can just keep doing this until we either find the element we are looking for, or we have only 1 element left in which case, the element we are searching for does not exist in this list.

size_t Algo_binary_search(int *input_list, size_t input_size, int search_item) {
  size_t left = 0;
  size_t right = input_size;
 
  while (left < right) {
    size_t mid = left + (right - left) / 2;
 
    if (input_list[mid] == search_item) {
      return mid;
    }
 
    if (input_list[mid] < search_item) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
 
  return -1;
}

In binary search, every iteration we devide our search size by half, and in the worst case scenario we would have to keep doing that until there is only 1 element left. So for first iteration we would be have $n$ elements to search, in the second we have the elements to $n/2$, in the third $n/4$ and so on till we only have 1 left, now let use assume that the last time we devided our input by half, it was our xth time deviding the input by half, so the sequence would look like

$n->n/2->n/4->n/8....->n/2^x$

So at the end(the xth iteration), it would look like we have devided the input by $2^x$ as we have devided the input by 2, x times. But since at the end there will only be 1 element left, it would mean:

$n/2^x=1$ and solving for x would provide us with: $x={\log }_2(n)$ since 2 is just a constant we can say that the time complexity of this algorithm would be: $O(\log (n))$

Space complexity is $O(1)$

Ternary Search

NOTE: this assumes that the provided input_list has already been sorted

• we first calculate left and right elements in the input_list with the following formulas: $\text{left middle}=\text{left}+\frac{\text{right}-\text{left}}{3}$ $\text{right middle}=\text{right}-\frac{\text{right}-\text{left}}{3}$
• Then we check if either of these middle values is the search_item
• if yes then hoorahh!
• On the other hand, if either of these is not equal to the item we are searching for, then we check 3 conditions:
  • if the item is smaller than left_middle
  • if the item is bigger than left_middle, and small than right_middle
  • if the item is bigger than right_middle
• let’s say the item is bigger than left_middle but smaller than right_middle, and since the input_list is sorted (assuming in accending order), we just proved that the element lies in the middle part
• so we can just discard the left and right parts altogether and just focus on the center part

We can just keep doing this until we find the element we are looking for.

int Algo_ternary_search(int *input_list, size_t input_size, int search_item) {
  if (input_size == 0) {
    return -1;
  }
 
  size_t left = 0;
  size_t right = input_size - 1;
 
  while (left <= right) {
    size_t mid_l = left + (right - left) / 3;
    size_t mid_r = right - (right - left) / 3;
 
    if (input_list[mid_l] == search_item) {
      return mid_l;
    }
    if (input_list[mid_r] == search_item) {
      return mid_r;
    }
 
    if (search_item < input_list[mid_l]) {
      right = mid_l - 1;
    } else if (search_item > input_list[mid_r]) {
      left = mid_r + 1;
    } else {
      left = mid_l + 1;
      right = mid_r - 1;
    }
  }
 
  return -1;
}

It is extremely similar to binary search, in terms of everything, the only difference being that instead of deviding by 2, we devide the input by 3, but still 2 or 3, they are both constants, so the time complexity be $O(\log (n))$

Space complexity is $O(1)$