Two of the biggest considerations when writing any code are memory usage and time complexity (speed). Big-O notation offers a framework to quantifying the relative memory and speed performance of the algorithm in terms of the size of the input \(n\). When comparing the performance of algorithms we want to remove the variability of the machines performance, and focus on the factors which influence an algorithms performance from a coding perspective.

Example Problem: Sudoku

The memory and time complexity of different algorithms change significantly depending on the problem being solved. Take a Sodoku puzzle for example, where \(n\) represent the width and height of the grid. Sodoku puzzles are considered to be very difficult problems when the size of the puzzle becomes larger. This is because there are more combinations to test in order to find the correct solution. This is also true for an algorithm, and therefore we can write the time complexity to solve a Sodoku puzzle in terms of the size of the grid \(n\).

Depth-first search (DFS) algorithm is used for tree traversal on graph or tree-like data structures. It can be implemented using recursion and data structures like dictionaries and sets in Python.

Breadth-first search (BFS) algorithm is used for tree traversal on graph or tree-like data structures. It is implemented in python with a queue that adopts a first-in-first-out policy.

Recursion in defined as the process of defining something in terms of itself. This means that a function can be used within its own function to create a stack which will be run in reverse order to which it is constructed (i.e. first-in-last-out). The factorial function below is a basic example of recursion in Python.

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

Example of Recursion to Calculate Factorial in Python

uint fibonacci(uint n) { 
	return n > 1 ? fibonacci(n-1) + fibonacci(n-2) : n; 
}  

Example of Recursion to Calculate Factorial in C++

One of the most common approaches to solve many algoritm problems is to apply some type of 2-Pointer approach. The 2-Pointer approach is used to search over a list (or multiple list) in such a way that the time complexity can be minimised. Consider the following problem:

Problem Statement: Given an array of positive integers and a positive target integer, return the minimal length of a contiguous sub-array of which the sum is greater than or equal to the target.

This article visually explains how we can use a two-pointer algorithm with a sliding window to solve this problem with \(O(n)\) time complexity.

List comprehension is a neat was to constuct a list in python within one line of code. The code below shows the general syntax for appending items using a loop.

for item in iterable:
  if condition == True:
    newlist.append(x)

By using list comprehension, this code can be reduced to:

newlist = [expression for item in iterable if condition == True]