Big-O Algorithm Complexity

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\).

Considerations

The two main considerations when determining the Big-O notation are:

• Does the problem get more difficult when the input space becomes larger or does it remain constant?
• Does the difficulty increase at a linear rate, log rate or some polynomial rate?

Big-O notation is generally written in terms of the input \(n\) when the difficulty of the problem increases as \(n\) becomes larger. In this event, the difficulty could increase at a log rate, linear rate, polynomial rate or exponential rate. The chart below has been taken from bigocheatsheet.com which illustrates the the relative performance of algorithms based on their Big-O notation, from \(O(1)\) being the best and \(O(n!)\) being the worst.

Relative Performance Represented using Big-O Notation

Its important to note that the relative performance of an algorithm is not fixed to one of these Big-O notations. For example, given a Sudoku puzzle and a set of inputs, the time it will actually take to solve the puzzle will partly depend on the which input values are given. For this reason we often refer to an algorithm as having an average Big-O notation of \(O(n \log n)\) for example. In some situations this algorithm may take \(O(n^2)\), depending on the inputs. Most sorting algorithms have an average Big-O notation and worst-case Big-O notation.

The P vs. NP Problem

I would like to briefly touch on a topic in mathematical and computer science which also relates to the time complexity of solving an problem using an algorithm. The P vs. NP Problem is one of the unproven mathematical problems with a $1m reward for any proof. This problem simply states that if a problem can be validated in polynomial time, then can it also be solved in polynomial time? NP time in this case stands for “Nondeterministic Polynomial” time. The diagram below has been taken from this useful article on the topic.

P vs. NP Problem

For the Sudoku problem, checking a solution is correct is generally done in \(O(1)\) while solving an unfinished Sudoku is \(O(n^m)\) where the grid is \(n \times n\) and there are \(m\) blank spaces. Notice that solving the problem requires an exponentially increasing amount of time when the problem becomes large while the time complexity to validate a solution is constant. The rate of increase of this exponential also depends on the number of missing squares to start with. It has also been shown that if an algorithm to solve a Sudoku puzzle in polynomial time exists, then it can also be used on other NP-complete problems.

Summary

Big-O notation is an important concept in order to understand the space and time complexity of an algorithm. Big-O notation can provide an indication of the relative time an algorithm will take to solve given the size of the input \(n\). There is a very important open problem in mathematics and computer science to understand the relationship between problems that are easy to check but hard to solve.