Big O Notation in C

Big O Notation in C: In the C programming language, we have so many algorithms and solutions to the problems that exist, which have different aspects and purposes to an algorithm. We have also understood the complexity of an algorithm and how to analyze whether the algorithm suits best, calculate an algorithm’s complexity, and so on.

It is essential to calculate the time and the space complexity of an algorithm. It can be concluded that the algorithm, which has taken little time and little space complexity, is considered to be the best algorithm of all. A developer also categorizes how to find the best case, the average case, and the algorithm's worst case. 

Hence, for analyzing such complexities and then representing them, the concept of the asymptotic notation has been used as it has different types available for representing such complexities. Big O Notation is considered to one such notation.

The mathematical notations that are used for analysis are asymptotic of many algorithms. The word asymptotic defines an expression where a variable exists, and the value tends to infinity.

In other words, it is a method that defines the limiting behavior of an expression. Henceforth, usage of the asymptotic notations makes us analyze the complexity of an algorithm and the performance of an algorithm.

Complexities can be determined after analyzing and using asymptotic notations. The asymptotic notations are divided into the following three types, which are used to analyze the complexities of the algorithms:

1. Big O Notation (O)

The Big O represents the upper bound of a runtime of the algorithm. The big O notation's vital role is to calculate the longest time the algorithm runs to execute a solution to a given problem; i.e., it is also used to calculate the algorithm's worst-case complexity.

• Theta Notation (?(n))

The theta carries the middle part of characteristics of Big O Notation and the Omega Notation as they represent the upper bound and lower bound of an algorithm, respectively.

• Omega Notation (?(n))

The omega notation represents the lower bound of the algorithm's runtime.  It is also used to calculate the best time an algorithm will take to complete the execution of a problem; that is, it is also used to measure the algorithm's best-case time complexity.

Big O Notation

The Big O is used to express the upper bound of the algorithm’s runtime. Hence, the worst-case time complexity can be measured of any algorithm a developer wants to. It also analyzed and calculated the time and amount of memory required to execute an algorithm for the input value.

Mathematically speaking, for a function, f(n) and another function g(n), where both the functions are defined on some unbounded set of the real positive numbers.

Here, g(n) is positive for all the large values of the ‘n’. Hence, it can be written as:

f(n) = O(g(n))

Where ‘n’ tends to infinity, that is (n ??).

It can be seen that the assumption of ‘n’ to infinity is left untouched, so that, we can write the expression from above as:

f(n) = O(g(n))

The functions f and g are necessary functions from the positive integer to a non-negative actual number. Hence, the Big O Notation generally refers to the large ‘n’ values.

The Big O notation is considered to be a constant factor. In the notation given above, if there are positive constants such as ‘n0’ and ‘c’ so that, to the right of ‘n0’, the function ‘f(n)’ will always lie on or below ‘c*g(n)’.

O(g(n)) = {f(n): there exist a positive constant c and n0 such that 0 <= f(n) <= c g(n),

for all n <= n0}

Properties of Big O Notation

• Constant multiplication:

If f(n) = c * g(n), then O(f(n)) = O(g(n)), where c is a non-zero constant.

• The Polynomial function:

If the function f(n)= x1 + x1 * n + x2 * 2 + x3 * 3 + x4 * 4 +… + xm * nm, then O(f(n)) = O(nm).

• The Logarithmic function:

If f(n) = log_a(n) and g(n) = log_b(n), then O(f(n)) =O(g(n)).

• The Summation function:

If f(n) = f ₁(n) + f ₂ (n) + f ₃(n) + f ₄(n) + f ₅(n) +  … +   f _m (n) + and f _i (n) < = f _i + 1(n),

where i = 1, 2, 3, 4, … , m; then

O(f(n)) = O (max (f1(n), f2(n), f3(n), f4(n), … , m(n))).