Data Structure and Algorithms 102: Deep Dive into Data Structure and Algorithms

From the previous article READ HERE I introduced data structures and algorithms. In this article we are going to go deep further and get to understand them more.

Introduction

For any given problem, there can be n number of solutions that can be used to solve it. Because of these multiple solutions, say for one problem we can get confused face another challenge, that is, which solution will we go for? To get an answer to this, we have to go for the solution that is fast and efficient in terms of consuming the computer resources, e.g memory Hence the need to understand:

1. Time complexity
2. Space complexity

1. Time complexity
This is the total time an algorithm takes to complete as a function of the length of input, i.e the number of operations to be performed.

Types of Time Complexity Notations

• Big-O
  It defines the worst case or upper bound of an algorithm Tells us the maximum amount of time required by an algorithm considering all input values. A function will never exceed a specified time.

• Omega
  It defines the best case or lower bound of an algorithm. Tells us the minimum amount of time required by an algorithm considering all input values.

• Theta
  It defines the average case of an algorithm's time complexity.

Types of Time Complexities

1. Linear time O(n): An algorithm's runtime will increase linearly with an increase in the input size n.
2. Constant time O(1): An algorithm's runtime will always be the same irrespective of the input size n.
3. Logarithmic time O(log n): As the size of input increase, the number of operations get reduced.
4. Cubic time O(n^3): An algorithm's runtime is proportional to the cube of the input values.
5. Quadratic time O(n^2): An algorithm's runtime will increase non-linearly with an increase in the input size n.

Time Complexity of searching algorithms

• Linear search

  (js)
const linearSearchAlg = (value, list) =>{
let ifFound = false;
let positionofValue = -1;
let index = 0;

while(!ifFound && index < list.length) {
        if(list[index] == value) {
            ifFound = true;
            positionofValue = index;
        } else {
            index += 1;
        }
    }
    return positionofValue;  
      }

Best case: O(1) - Achieved if the element being searched is the first element.
Worst case: O(n) - Achieved if the element being searched is the last element or if the element is not found in the list.

• Binary search
  For it to work, the list must be sorted

  const binarySearchAlg(value, list) {
  let leftMostPoint = 0;   
  let rightMostPoint = list.length - 1;  
  let positionofSearchedValue = -1;
  let ifFound = false;
  let midPoint;
  
  while (ifFound === false && leftMostPoint <= rightMostPoint) {
      midPoint = Math.floor((leftMostPoint +rightMostPoint)/2);
      if (list[midPoint] == value) {
          ifFound = true;
          positionofSearchedValue = mid;
      } else if (list[midPoint] > value) {  
          rightMostPoint = midPoint - 1;
      } else { 
          leftMostPoint = midPoint + 1;
      }
  }
  return positionofSearchedValue;
        }
  

Best case: O(1) - Achieved if the element being searched is in the middle of the array.
Worst case: O(log n) - Achieved if the element being searched is the last element or if the element is not found in the list.

2. Space complexity
This defines the amount of space or memory an algorithm takes to complete as a function of the length of input. For any algorithm, memory may be used for, storing variables, program instructions and execution.

Space Complexity of searching algorithms

• Linear search: Its space complexity is equal to the size of the array being searched.
• Binary search: Its space complexity is O(n).

Conclusion

Understanding time and space complexities is important in order to write efficient code.