This article describes some important principles to consider in algorithm design.

Divide and Conquer

Divide and conquer is an algorithm design system in which a problem is divided into sub problems until these subproblems can be solved independently. These sub problems are solved recursively and then combined until the whole problem is solved. This system is used in various popular algorithms such as the quick sort and merge sort.

Summarily, using this paradigm involves 3 process stages: divide, conquer and combine.

Corner Cases

Corner cases are situations that occur when an algorithm input may lead to unexpected or incorrect behavior. A simple example is as follows:

double divideValues(int a, int b) { return a / b; }

In the example, in the event that the value of b is 0, an error will be generated. To avoid this error, the possibility of b = 0 must be handled.

In designing algorithms it is important to consider, test for and handle possible corner cases.

Big O Notation

The Big O notation is used to evaluate or classify algorithms in terms of the time requirement and/or space requirement as the input grows i.e. it determines the time taken in execution or the space/ memory required by the algorithm with respect to its input values. The implementation details such as programing language, operating system, hardware properties..., are not considered in the evaluation.

For time complexity, the Big O notation is written as O(T(n)). T(n) represents a time complexity function that describes how the running time grows as the input n grows.

The O means that that the running time grows proportionately as the function in brackets.

It is important to note that this time complexity describes the running time for a worst-case scenario and for large input cases.

Some popular notations listed from best case to worst case are: O(1), O(log n), O(sqrt(n)), O(n), (n log n), O(n²).

The space complexity notations are same as those of time complexity except that in this case, the O notation now refers to the spatial increment and S is used instead of T.

In designing algorithms it is a good practice to design for efficiency, especially in the event of large input requirements. The Big O notation is an effective means of generating efficiency ratings.