“A heuristic technique, often called simply a heuristic, is any approach to problem solving, learning, or discovery that employs a practical method not guaranteed to be optimal or perfect, but sufficient for the immediate goals. Where finding an optimal solution is impossible or impractical, heuristic methods can be used to speed up the process of finding a satisfactory solution. Heuristics can be mental shortcuts that ease the cognitive load of making a decision. Examples of this method include using a rule of thumb, an educated guess, an intuitive judgement, guesstimate, stereotyping, profiling, or common sense.” (Source: Wikipedia)

“In computer science, a heuristic is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution. This is achieved by trading optimality, completeness, accuracy, or precision for speed. In a way, it can be considered a shortcut.” (Source: Wikipedia)

The objective of a heuristic algorithm is to apply a rule of thumb approach to produce a solution in a reasonable time frame that is good enough for solving the problem at hand. There is no guarantee that the solution found will be the most accurate or optimal solution for the given problem. We often refer the solution as “good enough” in most cases.

Heuristic Algorithms?

Let’s investigate a few basic examples where a heuristic algorithm can be used:

Noughts & CrossesGame of ChessTop TrumpsLanguage RecognitionShortest Path Algorithms

To help the computer make a decision as to where to place a token on a 3×3 noughts and crosses grid, a basic heuristic algorithm should be based on the rule of thumb that some cells of the grid are more likely to lead to a win:

Based on this approach, can you think of how a similar approach could be used for an algorithm to play:

• Othello (a.k.a. Reversi Game)
• A Battleship game?
• Rock/Paper/Scissors?

When playing a game of chess, expert players can “see” several moves ahead. It would be tempting to design an algorithm that could investigate every single possible move that players can make and investigate the impacts of such moves on the outcome of the game. However such an algorithm would have to investigate far too many possible moves and would quickly become too slow and too demanding in terms of memory resources in order to perform effectively.

It is hence essential to use a heuristic approach to quickly discard some moves which would most likely lead to a defeat while focusing on moves that would seem to be a good step towards a win!

Let’s consider the above scenario when investigating all the possible moves for this white pawn. Can the computer make a quick decision as to what would most likely be the best option?

Heuristic approaches do not always give you the best solution. Can you explain how this could be the case with this scenario?

Sometimes your algorithm need to collect or analyse data before applying heuristic to make a decision. This can be done by providing the computer with some data or by implementing an algorithm based on machine learning.

For instance in a game of Top Trumps, if your algorithm knows the average value of each card for each category, it will be able to select the criteria which is most likely going to win the round.

Alternatively, a machine learning algorithm could play the game and record and update statistics after playing each card to progressively learn which criteria is more likely to win the round for each card in the deck.
You can investigate how machine learning can be used in a game of Top Trumps by reading this blog post.

Heuristic methods can be used when developing algorithms which try to understand what the user is saying, or asking for. For instance, by looking for words associations, an algorithm can narrow down the meaning of words especially when a word can have two different meanings:

e.g. When using Google search a user types: “Raspeberry Pi Hardware” We can deduct that in this case Raspberry has nothing to do with the piece of fruit, so there is no need to give results on healthy eating, cooking recipes or grocery stores…

However if the user searches for “Raspeberry Pie ingredients”, we can deduct that the user is searching for a recipe and is less likely to be interested in programming blogs or computer hardware online shops.

Short Path Algorithms used by GPS systems and self-driving cars also use a heuristic approach to decide on the best route to go from A to Z. This is for instance the case for the A* Search algorithm which takes into consideration the distance as the crow flies between two nodes to decide which paths to explore first and hence more effectively find the shortest path between two nodes.

You can compare two different algorithms used to find the shortest route from two nodes of a graph:

• Dijkstra’s Shortest Path Algorithm (Without using a heuristic approach)
• A* Search Algorithm (Using a heuristic approach)

The question we will try to answer in this blog post is as follows: How can we measure the effectiveness/performance of an algorithm?

First let’s consider this quote from Bill Gates (Founder of Microsoft):

So, according to Bill Gates the length of a program (in lines of code) is not a criteria to consider when evaluating its effectiveness to solve a problem or its performance.

• A long program does not necessarly mean that the program has been coded the most effectively.
• And vice-versa, a shorter program does not necessarly perform better than a longer piece of code.

Big O Notation

The Big O notation is used in Computer Science to describe the performance (e.g. execution time or space used) of an algorithm.

The Big O notation can be used to compare the performance of different search algorithms (e.g. linear search vs. binary search), sorting algorithms (insertion sort, bubble sort, merge sort etc.), backtracking and heuristic algorithms, etc. It is especially useful to compare algorithms which will require a large number of steps and/or manipulate a large volume of data (e.g. Big Data algorithms).

Best Case, Average Case or Worst Case Scenario?

The Big O notation can be used to describe either the best case, average case or worst-case scenario of an algorithm. For instance, let’s consider a linear search (e.g. finding a user by its username in a list of 100 users). In the best case scenario, the username being searched would be the first username of the list. In this case the algorithm would complete the search very effectively, in just one iteration. However, the worst case scenario would be that the username being searched is the last of the list. In this case the algorithm would require 100 iterations to find it.

Considering that the average or worst case scenario, we can deduct that a linear search amongst N records could take up to N iterations. There is a linear correlation between the number of records in the data set being searched and the number of iterations of the average case and worst case scenarios.

In this case a linear search would have the following time complexity big O notation:

• Best Case Scenario:Constant Notation: O(1)
• Average Case Scenario: Linear Notation: O(N)
• Worst Case Scenario: Linear Notation: O(N)

So let’s review the different types of algorithm that can be classified using the Big O Notation:

O(1)O(N)O(N²)O(2^N)O(log(N))

Constant Notation: O(1)

The constant notation describes an algorithm that will always execute in the same execution time regardless of the size of the data set.

For instance, an algorithm to retrieve the first value of a data set, will always be completed in one step, regardless of the number of values in the data set.

FUNCTION getFirstElemnt(list)
    RETURN list[0]
END FUNCTION

A hashing algorithm is an O(1) algorithm that can be used to very effectively locate/search a value/key when the data is stored using a hash table. It’s a more effective way than using a linear search O(N) or binary search O(Log(N)) algorithm. (See example blog post on hashing algorithm for memory addressing)

Linear Notation: O(N)

A linear algorithm is used when the execution time of an algorithm grows in direct proportion to the size of the data set it is processing.

Algorithms, such as the linear search, which are based on a single loop to iterate through each value of the data set are more likely to have a linear notation O(N) though this is not always the case (e.g. binary search).

FUNCTION linearSearch(list, value)
    FOR EACH element IN list
        IF (element == value) 
			RETURN true
		END IF	
	NEXT
    RETURN false
END FUNCTION

Polynomial Notation: O(N²), O(N³), etc.

Polynomial algorithms include quadratic algorithms O(N²), cubic algorithms O(N³) and so on:

• O(N²) represents an algorithm whose performance is directly proportional to the square of the size of the data set.
• O(N³) represents an algorithm whose performance is directly proportional to the cube of the size of the data set.
• etc.

Algorithms which are based on nested loops are more likely to have a polynomial O(N²), or O(N³), etc. depending on the level of nesting.

PROCEDURE displayTimesTable()
	FOR i FROM 1 TO 10
		FOR j FROM 1 TO 10
			product = i*j 
			OUTPUT i + " times " + j + " equals " + product
		NEXT j
	NEXT i
END PROCEDURE

Typically, O(N²) algorithms can be found when manipulating 2-dimensional arrays, O(N³) algorithms can be found when manipulating 3-dimensional arrays and so on.

PROCEDURE emptyChessboardGrid()
	FOR row FROM 0 to 7
		FOR col FROM 0 to 7
			grid[row][col] = 0
		NEXT col
	NEXT row
END PROCEDURE

Most sorting algorithms such as Bubble Sort, Insertion Sort, Quick Sort algorithms are O(N²) algorithms.

Exponential Notation: O(2^N)

The exponential notation O(2^N) describes an algorithm whose growth doubles with each addition to the data set.

Backtracking algorithms which test every possible “pathway” to solve a problem can be based on this notation. Such algorithms become very slow as the data set increases.

Example of exponential algorithm: An algorithm to list all the possible binary permutations depending on the number of digits (bits).

Logarithmic Notation: O(log(N))

A logarithmic algorithm O(log(N)) is an algorithm whose growth decreases when the data set increase following a logarithmic curve. Logarithmic algorithms are hence quite efficient especially when processing large sets of data.

A binary search is a typical example of logarithmic algorithm. In a binary search, half of the data set is discarded after each iteration. Which means that an algorithm which searches through 2,000,000 values will just need one more iteration than if the data set only contained 1,000,000 values.

Use a logarithmic algorithm (based on a binary search) to play the game Guess the Number.