Word Builder

The next example is an algorithm that collects every combination of two-character strings built from an array of single characters. For example, given the array ["a", "b", "c", "d"], we’d return a new array containing the following string combinations:

	[
	'ab', 'ac', 'ad', 'ba', 'bc', 'bd',
	'ca', 'cb', 'cd', 'da', 'db', 'dc'
	]

Following is an implementation of this algorithm. Let’s see if we can figure out its Big O efficiency:

	def word_builder(array):
	collection = []

	for index_i, i in enumerate(array):
	for index_j, j in enumerate(array):
	if index_i != index_j:
	collection.append(i + j)

	return collection

Here we’re running one loop nested inside another. The outer loop iterates over each character in the array, keeping track of the index of i. For each index_i, we run an inner loop that iterates again over each character in the same array using the index index_j. Within this inner loop, we concatenate the characters at index_i and index_j, with the exception of when index_i and index_j are pointing to the same index.

To determine the efficiency of our algorithm, we once again need to determine what the N data elements are. In our case, as in the previous example, N is the number of items inside the array passed to the function.

The next step is to determine the number of steps our algorithm takes relative to the N data elements. In our case, the outer loop iterates over all N elements, and for each element, the inner loop iterates again over all N elements, which amounts to N steps multiplied by N steps. This is the classic case of O(N²) and is often what nested-loop algorithms turn out to be.

Now, what would happen if we modified our algorithm to compute each combination of three-character strings? For our example array of ["a", "b", "c", "d"], our function would return the following array:

	[
	'abc', 'abd', 'acb',
	'acd', 'adb', 'adc',
	'bac', 'bad', 'bca',
	'bcd', 'bda', 'bdc',
	'cab', 'cad', 'cba',
	'cbd', 'cda', 'cdb',
	'dab', 'dac', 'dba',
	'dbc', 'dca', 'dcb'
	]

Here’s an implementation that uses three nested loops. What is its time complexity?

	def word_builder(array):
	collection = []

	for index_i, i in enumerate(array):
	for index_j, j in enumerate(array):
	for index_k, k in enumerate(array):
	if (index_i != index_j and
	index_j != index_k and index_i != index_k):
	collection.append(i + j + k)

	return collection

In this algorithm, for N data elements, we have N steps of the i loop multiplied by the N steps of the j loop multiplied by the N steps of the k loop. This is N * N * N, which is N³ steps, which is described as O(N³).

If we had four or five nested loops, we’d have algorithms that are O(N⁴) and O(N⁵), respectively. Let’s see how these all appear on a graph:

Optimizing any code from a speed of O(N³) to O(N²) would be a big win since the code becomes exponentially faster. However, the algorithm above remains stuck at O(N³).