Linear

Binary Search Tree

A Binary Search Tree (BST) is a data structure in which each node has at most two children and maintains the property that for every node, the values in its left subtree are less than the node’s value, and the values in its right subtree are greater.

Breadth-First Search

Breadth-First Search is an algorithm for searching graph data structures. It starts at a specified source node and explores all its immediate neighbors before moving on to the next level of neighbors.

  • Time complexity is Linear, i.e. O(v + e)
  • Space complexity is Linear, i.e. O(v)
  • For large graphs the space complexity is described in terms of depth making it exponential, i.e. O(b^d)

Counting Sort

Counting Sort is a non-comparison-based sorting algorithm that sorts integers by counting the occurrences of each distinct value in a range and using this information to place elements in their correct positions. It works in 𝑂(𝑛+𝑘) time, where 𝑛 is the number of elements and 𝑘 is the range of the input values. Counting Sort is efficient for small ranges of integers but unsuitable for sorting non-integer or large-range data due to its space complexity of 𝑂(𝑘). It is a stable sorting algorithm when implemented correctly.

Linear Search

Linear Search is a straightforward algorithm for finding a specific element in a list. It sequentially checks each element until the target is found or the list ends, making it simple and effective for unsorted data but inefficient for large datasets.

Linked List

A data structure where each element contains a value and a reference to the next node, supporting efficient insertion and deletion operations.

  • Time complexity for access and search is Linear, i.e. O(n)
  • Time complexity for insertion and deletion is Constant, i.e. O(1)
  • Space complexity is Linear

Longest Common Prefix

An algorithm for finding the longest common prefix among a set of strings.

  • Time complexity is Linear, i.e. O(n)
  • Space complexity is Constant, i.e. O(1)

Merge Sort

A divide-and-conquer sorting technique that splits the array into halves, recursively sorts each half, and then merges the sorted halves.

  • Time complexity is Linearithmic, i.e. O(n log(n))
  • Space complexity is Linear, i.e. O(n)

Queue

A linear collection following the First-In-First-Out (FIFO) principle, supporting operations like enqueue and dequeue, useful in task scheduling.

  • Time complexity for access and search is Linear, i.e. O(n)
  • Time complexity for insertion and deletion is Constant, i.e. O(n)
  • Space complexity is Linear

Recursive Depth-First Search

A recursive depth-first search algorithm that explores branches deeply before backtracking, managing traversal state with recursion.

  • Time complexity of insertion and deletion is Constant, i.e. O(1)
  • Time complexity of search is is Linear, i.e. O(n)
  • Space complexity is Linear, i.e. O(n)

Reverse

The reverse algorithm takes an array of values and returns the values in reverse order. It works by iterating over the array and swapping the first and last values, then the second and second-to-last values, and so on until the middle of the array is reached.

Stack

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. Elements are added and removed from the same end, called the top. Common operations include push (add an element), pop (remove the top element), and peek (view the top element without removing it). Stacks are used in various applications like function call management, expression evaluation, and backtracking.

Suffix Array

The suffix array algorithm constructs a sorted array of all suffixes of a given string, enabling efficient substring searches, pattern matching, and text analysis. It uses sorting and optional auxiliary structures like the LCP array for additional optimizations.