Complexity Functions in algorithm analysis

Time is usually the most critical resource considered in algorithm analysis. With most algorithms, the running time typically increases with the size of input.

Complexity functions are used to express the relationship between the size of input and the time taken by an algorithm to complete its task.

The functions describe the growth rate of an algorithm's time usage as a function of the input size, n.This help in understanding the efficiency of an algorithm and how well it scales as  the size of input grows. 

In the following parts we will look at the most commonly used functions in algorithm analysis.

The Constant Function

The constant function is the most basic of the complexity functions. It indicates that the performance of an algorithm remains constant regardless of the input size.To put it better, algorithm's performance does not depend on the size of input.

It can be expressed as follows:

Where n is the input size and c is a constant. The most common manifestation of this function is with the constant being 1, as in.

This function is considered efficient and desirable in most of the cases.

For example, accessing an element at any position of an array can be done in a fixed time, regardless of the size of the array. This is an example of a constant time complexity.

The logarithm Function

The logarithm function is the most interesting of the time complexity functions. It arises in a stuation where an algorithm divides the problem into smaller subproblems at each step.

This function indicates that the running time of an algorithm grows logarithmically with the size of the input (n).

It is represented as shown below:

In computer science, logarithms are usually expressed with a base of 2. So in most cases, the logarithm function will be represented as follows,

This implies that if x is the time taken by an algorithm to accomplish a task, then.

According to basic laws of logarithms, this leads to:

The logarithm complexity function is highly desirable for certain types of algorithms due to its efficiency. It is normally used in scenarios where divide-and-conquer strategies are needed.

The binary search algorithm is a basic axample of the logarithm complexity function. 

Binary search is used to efficiently locate an element in a sorted array. With each failed search, it reduces the search elements by half, by discarding either the left or right potion of the remaining array.

The Linear Function

The linear function is one of the most common complexities in algorithms. It arises when the running time of an algorithm increases linearly with the size of input. 

It is represented as:

The most obvious example of a linear function complexity is when traversing through an array, performing an action with each element. 

The NLogN Function

The nlogn function, arises in cases where the time taken by an algorithm grows at a rate proportional to the product of the input size (n) and the logarithm of the input size (log2n). It is normally encountered in sorting algorithms that involves the devide-and-conquer strategy.

It is expressed as;

This function usually grows at a faster rate than the linear function but at a much slower rate than the quadratic function.

The Quadratic Function

The quadratic function is encountered in cases where the time complexity of an algorithm grows proportionally to the square of the input size (n). This typically happens with nested loops.

The function is expressed as:

This function tends to grow at a very rapid rate as the input size increases. This is why it is generally advisable to avoid using nested loops when dealing with large datasets.

The Cubic Function

This Cubic function is relatively rare  compared to other functions of lower complexites. It arises in algorithms where the time complexity grows with the cube of the input size (n).

It is expressed as,

This function is usually encountered in triple-nested loops:

for i in dataset:
    for j in dataset:
         for k in dataset:
              ....

This function should generally be avoided.

The Exponential Function

The exponential function is expressed as,

The function describes an algorithm whose operations increases exponentially with the size of input. As the input size grows, the time taken by the algorithm tends to increase enormously, making such algorithms highly inefficient, even for relatively small input sizes.

The exponential function is generally impractical for most real-world applications.