Algorithms & Complexity

The Logic of Action: What is an Algorithm?

In computer science, an **algorithm** is a self-contained, step-by-step sequence of instruction parameters designed to perform a specific task, solve a logical problem, or perform a calculation. Every program on your computer, every app on your phone, and every service on the internet is fundamentally composed of algorithms. Whether it is Google Maps calculating the fastest traffic-aware route, Amazon recommending products, or a cryptography module securing a bank transfer, algorithms are the logic engine of code.

To be considered a valid algorithm, a sequence of steps must satisfy several core characteristics:

• Finiteness: The algorithm must terminate after a finite number of steps; it cannot run in an infinite loop.
• Definiteness: Each step must be clear, unambiguous, and precisely defined.
• Input & Output: It must accept zero or more inputs, and produce at least one defined output.
• Effectiveness: Each step must be simple enough to be performed mentally or using a pen and paper in a finite duration.

Measuring Efficiency: Big O Notation

If you have two different algorithms that solve the exact same problem, how do you decide which one is better? Computer scientists measure algorithm performance using **Big O Notation**. Big O measures how the execution time or memory space of an algorithm scales as the size of the input data (represented as n) grows toward infinity. It focuses on the **worst-case scenario**, representing the maximum bounds of execution.

Common Complexity Classes (Fastest to Slowest)

• O(1) - Constant Time: The execution time remains identical, regardless of the input data size. Example: accessing an array element by its index, or checking if a number is even or odd.
• O(log n) - Logarithmic Time: The execution time halves with each step. Algorithms in this class are exceptionally fast, especially for large inputs. Example: Binary Search.
• O(n) - Linear Time: Execution time grows in direct, 1-to-1 proportion with the input size. Example: finding a specific value in an unsorted list by checking every element.
• O(n log n) - Linearithmic Time: Slightly slower than linear time, typical of efficient sorting algorithms. Example: Merge Sort, Heap Sort.
• O(n²) - Quadratic Time: Execution time grows quadratically, typical of nested loops. Double the input size, and execution time increases fourfold. Example: Bubble Sort, Selection Sort.
• O(2ⁿ) - Exponential Time: Execution time doubles with every single addition to the input size. These algorithms quickly become unrunnable even for small inputs. Example: solving the Traveling Salesperson Problem using brute force.

Searching Algorithms: Finding Data

Searching is the process of finding the location of a target element within a collection of data. The two primary techniques represent a key trade-off:

1. Linear Search (Sequential Search)

The simplest search method. The algorithm starts at the beginning of a list and checks each element one by one until it finds the target or reaches the end. It has a time complexity of **O(n)**. Its main advantage is that it works on both sorted and unsorted lists.

2. Binary Search (Divide and Conquer)

An exceptionally fast search algorithm that operates on the divide-and-conquer principle. **Binary Search requires the list to be pre-sorted.** The algorithm compares the target value to the middle element of the array:

1. If the target matches the middle element, the search is complete.
2. If the target is smaller, the algorithm discards the right half of the array and repeats the search on the left half.
3. If the target is larger, it discards the left half and repeats on the right.

By halving the search space at each step, Binary Search achieves a time complexity of **O(log n)**. Searching a database of 1 million sorted records takes at most 20 comparisons using Binary Search, compared to up to 1 million checks using Linear Search.

Sorting Algorithms: Ordering Data

Sorting is the process of arranging elements in a logical order (e.g., ascending numbers or alphabetical letters). Different sorting algorithms offer various trade-offs in speed, memory usage, and stability:

Bubble Sort (Quadratic)

A simple, comparison-based algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process repeats until the list is sorted. Because it requires nested loops, its worst-case complexity is **O(n²)**, making it highly inefficient for large datasets.

Insertion Sort (Quadratic)

Operates similarly to sorting a hand of playing cards. It iterates through the list, picking one element at a time and inserting it into its correct position within the sorted subset. While worst-case is **O(n²)**, it is highly efficient for small datasets or lists that are already nearly sorted, where it runs in **O(n)** time.

Merge Sort (Linearithmic)

A recursive, divide-and-conquer sorting algorithm. It divides the unsorted list into n sub-lists (each containing 1 element), then repeatedly merges sub-lists back together in sorted order until only a single sorted list remains. It guarantees a time complexity of **O(n log n)** in all cases (best, average, and worst) but requires extra memory space (**O(n)**) to hold the temporary merged sub-lists.

Quick Sort (Linearithmic / Quadratic)

Another divide-and-conquer algorithm. It selects a "pivot" element from the array and partitions the other elements into two sub-arrays, depending on whether they are smaller or larger than the pivot. It then recursively sorts the sub-arrays. Quick Sort is extremely fast in practice, averaging **O(n log n)**. However, if the pivot selection is poor (e.g., picking the smallest element in an already sorted list), its complexity degrades to **O(n²)**.

Sorting Algorithm Complexity Comparison

The table below summarizes and compares the performance characteristics of the primary sorting algorithms:

Frequently Asked Questions

What's Next?

Now that you know how to build efficient algorithms, you can explore how large volumes of structured data are stored permanently in databases. Read Database Management Systems (DBMS) to explore relational structures, SQL queries, and normalization.