Get this book > Matrix Problems: For Interviewing and Competitive Programming
Reading time: 30 minutes
In this article we will understand the complexity notations for algorithms along with BigO, BigOmega, BTheta and LittleO and see how we can calculate the complexity of any algorithm.
The notations we use to describe the asymptotic running time of an algorithm are defined by functions whose domain is the set of natural numbers $\mathbb{N} = {0, 1, 2,...}.$ Such Notations are useful for describing the worstcase runtime function $T(n)$, which is usually only defined for integer inputs. Computer scientists make extensive use of specialized asymptotic notations to approximate the growth of functions.
We examine the following subtopics:
 BigONotation, BigOmega und BigThetaNotation
 small O notation
 How to calculate the complexity of any algorithm
Intuition
Asymptotic notation provides the basic vocabulary for discussing algorithm design and analysis. For us algorithm lovers, it's important to know what programmers mean when they say that one piece of code runs in "big On time" while another piece runs in "big On time squared".
This vocabulary is so ubiquitous because it identifies youRight place
to argue about algorithms. The asymptotic notation isthick enough
Suppress any details that we want to ignore, details that depend on architecture choice, programming language choice, compiler choice, and so on. On the other hand, it isnecessary
enough to make useful highlevel comparisons between different algorithmic approaches to solving a problem, especially for larger inputs (the input that requires algorithmic ingenuity).
For example, asymptotic analysis helps us distinguish between better and worse approaches to sorting, multiplying two integers, and so on.
High level idea:
If you ask a practicing programmer to explain the sense of asymptotic notation, he will probably say something like this:
The basic idea of asymptotic notation is to suppress constant factors and lowerorder terms.
constant factors  very system dependent
Lowerorder terms: irrelevant for large inputs
Example: Combine $6nlog_2n + 6$ with only $nlogn$.
Terminology:The runtime is $O(nlogn)$ $["bigOh"\mbox{of} nlogn]$
where $n$ = input size (e.g. input array length)
examples
 Search for an array:
Verboten
: Array $A$ of integers and an integer $t$.
Production
: whether or not $A$ contains $t$.
for i:= 1 to n do if A[i] = t then return TRUE return FLASSE
We didn't formally define whatbig O rating
still means but
From our intuitive discussion so far, you can guess that
asymptotic running time of the code above.
Asymptotic running time  $O(n)$
 Find two fixes:
Verboten
: Arrays $A$ and $B$ each with n integers and an integer t.
Production
: Whether or not $A$ or $B$ contains t.
do for i:= 1 to n if A[i] = t then return TRUE for i:= do 1 to n if B[i] = t then return TRUE
Asymptotic running time  $O(n)$
 duplicate check:
Verboten
: Array of n integers.
Production
: whether or not $A$ contains an integer more than once.
for i := 1 to n do for j := i + 1 to n do if A[i] = A[j] luego regresa TRUEreturn FALSE
Asymptotic running time  $O(n^2)$
2. Big O notation
Definition:
Definition in English:
BigO notation gives the maximum time an algorithm takes for all input values.
Let $T(n)$ = function at n = 1, 2, 3,... [generally the worst running time of an algorithm]
$T(n) = O(f(n))$ if and only if $T(n)$ is ultimately bounded by a constant multiple of $f(n)$ (asymptotic upper bound).
Image definition::
$T(n)$ is not bounded by $f(n)$ above, but multiplying $f(n)$ by 3 causes the top dashed line to pass over $T(n)$ once we get far go right enough on the graph, past the "crossover point" at $n_0$. since $f(n)$ is indeed bounded by a constant multiple of $f(n)$, we can say that $T(n) = O(f(n))$.
MatheDefinition:
$T(n) = O(f(n))$ if and only if $\exist$$ positive constants $c, n_0$ such that
$$T(n) \leq c.f(n) \mbox{ [2.1]}$$
$$\forall n\geq n_0$$
Trial:
Agame theory
Outlook.
For example, let's prove that $T(n) = O(f(n))$ to prove that the asymptotic running time of an algorithm is linear in input size (equivalent to $f(n) = n $ ) , i.e our task to choose the constants $c$ and $n_0$ such that $[2.1]$ lasts as long as $n \geq n_0$.
One way to think of it as game theory is as a competition between you and an opponent. You go first and need to commit to the $c$ and $n_0$ constants. Your opponent finishes second and can choose any integer $n$ that is at least $n_0$. You win if $[2.1]$ holds, your opponent wins if the opposite inequality $T(n) \geq c f(n)$ holds.
If $T(n) = O(f(n))$ then there are constants $c$ and $n_0$ such that $[2.1]$ holds for all $n \geq n_0$ and you have a winning strategy
in this game. Otherwise, no matter how you choose $c$ and $n_0$, yours
the opponent can choose $n\geq n_0$ large enough to reverse the inequality and win the game.
note: When we say that $c$ and $n_0$ are constants, we mean that they cannot depend on n. For example, in the figure $[2.1]$ $c$ and $n_0$ were fixed numbers (like 3 or 1000), and so we consider the inequality $[2.1]$ when n increases arbitrarily (looking to the right in the graph to infinity). If we never catch ourselves saying "take $n_0 = n$" or "take $c = \log_2n$" as a supposed BigO test, we should be left with the options that $c$ and $n_0$ are independent are, start over $n$.
Example:
claim
: if $T(n) = a_kn^k + ... + a_1n + a_0$ then $T(n) = O(n^k)$court hearing
: Elija $n_0 = 1$ y $c = a_k + a_{k1} + ... + a_1 + a_0$
Show exactly that $\forall n \geq 1, T(n) \leq c.n^k$
For every $n \geq we have 1$
$$T(n) \leq a_kn^{k} + ... + a1n + a_0$$
$$\leq a_kn^{k} + ... + a1n^k + a_0n^k$$
$$ = c.n^k $$
Then by Theorem $[2.1]$ we can say that the statement is true.
3. BigOmega und BigThetaNotation
big o notation
is by far the most important and ubiquitous concept to discuss the asymptotic running time of algorithms. A few of his close relatives whobig omega
jbig boob
Notations, it is also worth knowing them. If bigO is analogous to "less than or equal to ($\leq$)", then bigomega and bigtheta are analogous to "greater than or equal to ($\geq$)" and "equal to ( =)" , respectively Let's be more specific about them now.
Big Omega Notation:
Definition:
definition in english:
$T(n)$ is a major omega of another function $f(n)$ if and only if $T(n)$ is finally bounded below by a constant multiple of $f(n)$. In this case we write $T(n) = \Omega(f(n))$. As before, we use two constants $c$ and $n_0$ to quantify "multiple constants" and "possibly".
pictorial definition:
The $f(n)$ function does not bottombound $T(n)$, but if we multiply it by the constant $c = 14$, the result (the bottom dashed line) bottombounds $T(n)$ to continue to all $n$ beyond the crossing point at $n_0$. Then $T(n) = \Omega(f(n))$.
mathematical definition
$T(n) = \Omega(f(n))$ if and only if $\exist$$ positive constants $c, n_0$ such that
$$T(n) \geq c.f(n) \mbox{ [3.1]}$$
$$\forall n\geq n_0$$
BigThetaNotation:
Grand theta notation, or simply theta notation, is analogous to "equals". Saying that $T(n) = \Theta(f(n))$ means that $T(n) = \Omega(f(n))$ and $T(n) = O(f(n)) ) ps Finally, $T(n)$ is placed between two different constant multiples ($c_1, c_2$) of $f(n)$.
mathematical definition:
$T(n) = \Theta(f(n))$ if and only if $\exist$ positive constants $c_1, c_2, n_0$ such that
$$c_1.f(n) \leq T(n) \leq c_2.f(n) \mbox{ [3.2]}$$
$$\forall n\geq n_0$$
4. Little O notation
There is a final part of the asymptotic notation: "small o notation
“
What do you watch from time to time? If the big O notation is analogous
"less than or equal to", the lowercase o notation is analogous to "strictly less than".
MatheDefinition:
$T(n) = o(f(n))$ if and only if $\exist$$ positive constants $c, n_0$ such that
$$T(n) \leq c.f(n) \mbox{ [4.1]}$$
$$\forall n\geq n_0$$
Where does the notation come from?
Asymptotic notation was not invented by computer scientists; has been used in number theory since the beginning of the 20th century. Donald E. Knuth, the grandfather of formal algorithmic analysis, proposed using it as the standard language for analyzing growth rates and algorithm running times in particular.
“Based on the issues discussed here, I propose that SIGACT 8 members and editors of computer science and mathematics journals adopt the notations $O$, $\Omega$, and $Theta$ as defined above, unless it can better alternative will be found very soon".
5. How to calculate the complexity of any algorithm
Let's calculate the asymptotic complexity of algorithms...
The flow of the algorithm can be of two types.
 Iterative
 recursively
1. Iterative:
First, let's look at simple programs that don't contain any function calls. The rule of thumb for finding an upper limittemporal complexityof such a program is:
 estimate the maximum number of times each loop can be executed,
 Add these boundaries to cycles that follow each other.
 multiply these bounds for nested loops/chunks of code,
Example 1. Estimating the time complexity of a random piece of code
resultado int = 0; // 1 para (int i = 0; i < N; i++) // 2 para (int j = i; j < N; j++){ // 3 para (int k = 0; k < M; k++){ // 4 entero x = 0; // 5 while(x < N){ resultado++; x+= 3; } // 6 } // 7 for (int k = 0; k < 2*M; k++) // 8 if (k%7 == 4) resultado++; // 9} // 10
The time complexity of the while loop in line 6 is clearly $O(N)$: it runs no more than $\frac{N}{3} + 1$ times.
Now consider the for loop in lines 47. The variable $k$ is uniquely incremented $O(M)$ times. Therefore, each time the entire while loop of line 6 is executed, the total time complexity of lines 47 can be limited by $O(MN)$.
The time complexity of the for loop in lines 8 and 9 is $O(M)$. Therefore, the running time of lines 49 is $O(MN + M) = O(MN)$.
This inner part is executed $O(N^2)$ times, once for each possible combination of $i$ and $j$. (Note that there are only $\frac{N(N+1)}{2}$ possible values for $[i, j]$. However, $O(N^2)$ is a correct valueupper limit
.)
From the above facts it follows that thetotal time complexity
from the algorithm of Example 1, $O(N^2.MN) = O(MN^3)$.
Let's take another example. What will be the runtime complexity of the following code?
for(int i = 1; i <= n; i++){ //...}
For i = 1, number of operations = $2^{0}$, for i = 2, #operations = $2^{1}$, likewise for i = n, #operations = $2^{k}$, then $2^ {k} > n$, i.e. k = $log_{2}{n}$. Thus the time complexity is $O(\log_{2}{n})$ < logarithm.
Hence we can calculate the runtime complexity of any iterative algorithm.
Now go to the next part, How to calculate the time complexity of recursive algorithms.
1. Recursive:
 We're trying to build a recursive relationship and trying to extract the runtime complexity from that relationship.
Let's find the recursive relation for the following given program
fun(){ if(n > 1) return f(n  1) // Basisfall return n; // rekursiver Fall}
Looking at the function, we can evaluate and find the solution as shown below.
$$T(n) = { 1 + T(n1), \mbox{ if } n > 1} \mbox{ //rekursiver Fall}$$
$$T(n) = {1 , \mbox{ sim } n = 1} \mbox{ //caso base}$$
Methods to resolve recursive relationships:
for). Subsequent exchange procedure
b). Recursion Tree Method
A).Subsequent exchange procedure:
We expand the relationship and calculate the value of the variable using base cases and put it back in the original relationship to find the time complexity.
Let's see how this works.
$T(n) = 1 + T(n  1)$, then
$T(n  1) = 1 + T(n  2)$
$....$
$T(n) = 1 + 1 + T(n  2) => 1 + 1 + 1 + ... + T(n  k)$ where $k$ times the sum of 1, so we get finally
$T(n) = k + T(n  k)$, here for observation $k$ is the number of recursive calls. That means $T(1) = 1$ (the base case can be used) and then either $n  k = 1$ or $k = n  1$. We have $T(n) = n  1 + T(1) => T(n) = n$.
usebigoh
we can say time complexity $T(n) = O(n)$.
B).Recursion Tree Method:
We're trying to build a recursion tree to get a recursive relationship and then find a solution.
Steps:
 Draw an iteration tree based on the provided iteration relationship.
 Determine
 cost of each level
 Total number of levels in the recursion tree
 Number of nodes in the last level (#leaves)
 Last level cost
 Add up the cost of everyone
levels
of the recursion tree and simplify the resulting expression in asymptotic notation.
Let's look at a quick example
f(n){ if(n > 1){ for(int i = 0; i < n; i++) // n operations cout << "OpenGenus Foundation" << endl; intl = f(n/2) + f(n/2); // recursive case returns 1; } returns 1; // base case }
If we look at the problem, we can see that
 A problem of size n is broken down into 2 subproblems of size $\frac{n}{2}$.
 Then each subproblem of size $\frac{n}{2}$ is divided into 2 subproblems of size $\frac{n}{4}$ and so on.
 In the bottom layer, the size of the subproblems is reduced to 1
This can be represented in the form of a recursion tree.
Thus the recursive relationship for this problem will be as follows
$$T(n) = 1, \mbox{ sim n = 1} \mbox{ //caso base}$$
$$T(n) = n + 2T(\frac{n}{2}), \mbox{ if n > 1} \mbox{//recursive case}$$
The given repetition relation shows:
 The cost of splitting a problem of size $n$ into its 2 subproblems and then combining their solutions is n.
 The cost of splitting a problem of size $\frac{n}{2}$ into its 2 subproblems and then combining their solutions is $\frac{n}{2}$ and so on.
This is illustrated by the following recursion tree, where each node represents thecost
of the correspondentsub problem

Now determine the cost of each level.
 Level 0 cost = $n$
 Level 1 cost = $\frac{n}{2} + \frac{n}{2} = n$
 Level 2 cost = $\frac{n}{4} + \frac{n}{4} + \frac{n}{4} + \frac{n}{4} = n$ and so on.
Now determine the total number of levels in the recursion tree.
 Size of subproblem at level 0 = $\frac{n}{2^{0}}$
 Size of the subproblem at level 1 = $\frac{n}{2^{1}}$
 Size of the subproblem at level 2 = $\frac{n}{2^{2}}$
Likewise, we have the size of the subproblem on the level $i$ = $\frac{n}{2^{i}}$.
Suppose at level$k$ (last level) the subproblem size becomes 1. Then
$$\frac{n}{2^{k}} = 1$$
$$2^{k} = n$$
If we take the logarithm of both sides, we get
$$k\log_{2}2 = \log_2(n)$$
$k = \log_{2}(n)$
$\so$Total number of levels in the recursion tree = $\log_{2}{n} + 1$
Now determine the number of nodes in the last level.
 Level 0 has $2^{0}$ nodes, so 1 node
 Level 1 has $2^{1}$ nodes, i.e. 2 nodes
 Layer 2 has $2^{2}$ nodes, i.e. 4 nodes
If we continue in the same way, we have level $\log_{2}{n}$ has $2\log_{2}{n}$ nodes, so $n$ nodes
Determine the cost of the last level
Last stage cost = $n\ast T(1) = \Theta(n)$
Add up the costs of all levels of the recursion tree and simplify the resulting expressionAsymptotische Notation

$$T(n) = {n + n + n + ... + n} + \Theta(n)$$
where the sum of all $n$ for $\log_{2}{n}$ levels/depth.
$=> n\astlog_{2}{n} + \Theta(n)$
$=> nlog_{2}{n} + \Theta(n)$
$=> \Theta(nlog_{2}{n})$
So we can say that the asymptotic runtime complexity for this problem is $T(n) = \Theta(nlog_{2}{n})$
Using the same method, we can calculate the asymptotic time complexity of many algorithms like 'quick sort', 'merge sort', etc.
Computational Complexity Comparison:
In the graphical view...
The purpose of the asymptotic notation is to suppress constant factors (which are very system dependent) and lower order terms (which are irrelevant for large inputs).
A function $T(n)$ is called "uppercase O of $f(n)$", written "$T(n) = O(f(n))$", if it finally is (for $ n$ ) bounded above by a constant multiple of $f(n)$. That is, there are positive constants $c$ and $n_0$ such that $T(n) \leq c f(n)$ holds for all $n \geq n_0$.
A function $T(n)$ is "big omega of $f(n)$", written "$T(n) = \Omega(f(n))$", if it is finally bounded by a constant multiple of $f(n)$.
A function $T(n)$ is "big theta of $f(n)$", written "$T(n) = \Theta(f(n))$", if both $T(n) = 0 ( f(n))$ and $T(n) = \Omega(f(n))$.
A bigOR statement is analogous to "less than or equal to", bigomega to "greater than or equal to", and bigtheta to "equal to".
Let $f$ and $g$ be nondecreasing realvalued functions defined on the positive integers, where $f(n)$ and $g(n)$ are at least 1 for all $n \geq 1$. Suppose $f(n) = O(g(n))$ and let $c$ be a positive constant. Is $f(n) log_2(f(n)^{c}) = O(g(n) log_2(g(n)))$?
a) Yes, for all $f$, $g$ and $c$
b) Never, no matter what $f$ , $g$ and $c$ are
c) Sometimes yes, sometimes no, depending on the constant $c$
d) Sometimes yes, sometimes no, depending on the $f$ and $g$ functions
a) Since the constant c in the exponent lies within the logarithm, it becomes part of the main constant and is suppressed using BigOh notation.
references:
 Introduction to Algorithms, Thomas H. Cormen
 Specialization in Stanford algorithms
 CON OpenCourseWare