Time Complexity Analysis

Exploring time complexity and performance in a grouping algorithm.

This project explores various ways of solving a common problem that is presented to engineers, either in an interview setting or during the course of their work.

In this instance, we have an array of 3 letter strings that need to be grouped according to them being anagrams of each other.

Given an input of ['act', 'ten', 'zyx', 'net', 'cat', 'xyz'], the expected output should be ['act', 'cat', 'net', 'ten', 'xyz', 'zyx'].

To solve this, a series of functions were written with different approaches. Some contained more looping than others and were much slower to run.

Each of these functions delivered the same solution but with decreasing time complixity. Each iteration contained less for-loops.

The slower functions that contained more loops would take around 2,200ms to run over a dataset of 5000 randomised inputs. The most optimised function could process the same inputs in 18ms.

The source code for this project is available on GitHub at https://github.com/matfin/algorithms.