How is the complexity of an algorithm calculated? (+ different notations) (2023)

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 Big-O, Big-Omega, B-Theta and Little-O 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 worst-case run-time 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:

  • Big-O-Notation, Big-Omega- und Big-Theta-Notation
  • 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 placeto argue about algorithms. The asymptotic notation isthick enoughSuppress 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 isnecessaryenough to make useful high-level 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 lower-order terms.

constant factors - very system dependent
Lower-order terms: irrelevant for large inputs

Example: Combine $6nlog_2n + 6$ with only $nlogn$.

Terminology:The runtime is $O(nlogn)$ $["big-Oh"\mbox{of} nlogn]$
where $n$ = input size (e.g. input array length)

examples

  1. 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 ratingstill means but
From our intuitive discussion so far, you can guess that
asymptotic running time of the code above.
Asymptotic running time - $O(n)$

  1. 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)$

  1. 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:-

Big-O 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:-:

How is the complexity of an algorithm calculated? (+ different notations) (2)

$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))$.

Mathe-Definition:-

$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 theoryOutlook.

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 Big-O 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_{k-1}| + ... + |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_k|n^{k} + ... + |a1|n + |a_0|$$
$$\leq |a_k|n^{k} + ... + |a1|n^k + |a_0|n^k$$
$$ = c.n^k $$

Then by Theorem $[2.1]$ we can say that the statement is true.

3. Big-Omega- und Big-Theta-Notation

big o notationis by far the most important and ubiquitous concept to discuss the asymptotic running time of algorithms. A few of his close relatives whobig omegajbig boobNotations, it is also worth knowing them. If big-O is analogous to "less than or equal to ($\leq$)", then big-omega and big-theta 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:-

How is the complexity of an algorithm calculated? (+ different notations) (3)

The $f(n)$ function does not bottom-bound $T(n)$, but if we multiply it by the constant $c = 14$, the result (the bottom dashed line) bottom-bounds $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$$

Big-Theta-Notation:-

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".

Mathe-Definition:-

$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.

  1. Iterative
  2. 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 4-7. 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 4-7 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 4-9 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 complexityfrom 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(n-1), \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$.
usebig-ohwe 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:-

  1. Draw an iteration tree based on the provided iteration relationship.
  2. Determine-
  • cost of each level
  • Total number of levels in the recursion tree
  • Number of nodes in the last level (#leaves)
  • Last level cost
  1. Add up the cost of everyonelevelsof 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 sub-problems 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.
How is the complexity of an algorithm calculated? (+ different notations) (4)
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 thecostof the correspondentsub problem-
How is the complexity of an algorithm calculated? (+ different notations) (5)

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 sub-problem at level 1 = $\frac{n}{2^{1}}$
  • Size of the sub-problem 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:
How is the complexity of an algorithm calculated? (+ different notations) (6)

In the graphical view...
How is the complexity of an algorithm calculated? (+ different notations) (7)

  1. 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).

  2. 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$.

  3. 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)$.

  4. 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))$.

  5. A big-OR statement is analogous to "less than or equal to", big-omega to "greater than or equal to", and big-theta to "equal to".

Let $f$ and $g$ be non-decreasing real-valued 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 Big-Oh notation.

references:-

  1. Introduction to Algorithms, Thomas H. Cormen
  2. Specialization in Stanford algorithms
  3. CON OpenCourseWare
Top Articles
Latest Posts
Article information

Author: Merrill Bechtelar CPA

Last Updated: 03/18/2023

Views: 6319

Rating: 5 / 5 (70 voted)

Reviews: 93% of readers found this page helpful

Author information

Name: Merrill Bechtelar CPA

Birthday: 1996-05-19

Address: Apt. 114 873 White Lodge, Libbyfurt, CA 93006

Phone: +5983010455207

Job: Legacy Representative

Hobby: Blacksmithing, Urban exploration, Sudoku, Slacklining, Creative writing, Community, Letterboxing

Introduction: My name is Merrill Bechtelar CPA, I am a clean, agreeable, glorious, magnificent, witty, enchanting, comfortable person who loves writing and wants to share my knowledge and understanding with you.