How to prove the asymptotic order of an algorithm?

Question

Considering an algorithm like the one below:

function somaMatriz(matA, size) {
  let soma = 0;                                        // 1
  for(let i = 0; i < size; i++){                       // n + 1
    for(let j = 0; j < size; j++){                     // n(n + 1)
      soma += a[i][j];                                 // (n.n)
    }
  }  
  return soma;                                         // 1 
}

In a somewhat detailed analysis - considering unit cost and uniform - the expression referring to cost would be something like:

T(n) = 3 + 2n + 2n²

However, it can easily be noted that T(n) belongs to O(n²).

I know the asymptotic order doesn’t mean literally that this function (in this case, n²) dominates the original function (in this case, 3 + 2n + 2n²), but there is a constant - which I will call c - and an "initial" value of n — which I will call m - such that:

^{Considering n² as f(n) and 3 + 2n + 2n² as g(n).}

cf(n) dominate asymptotically g(n) from a given m.

In the case of the example, one can see it quite easily. Taking c as 3 and m as 4, one has:

3 + 2 * 4 + 2 * 4² = 43

and

3 * 4² = 48

And from this on (n 4), for any possible value of n the function cf(n) domina g(n).

But how can this be proved mathematically? In the above case, for example, I did it in trial and error (and then checked the examples of a book).

For example, even to try to standardize the possible answers, how to prove that:

5n² + 3n O(n²)

Answer 1

I’m going to give a short answer regarding only the proof, although Jefferson has already spoken (and very well) of complexities, domains, associated notations, etc.

Prove that a function c.g(n) domina f(n) from a given n and c.

Being f(n) a quadratic function as the given example, 5n^2 + 3n, we can formally define it as:

Then we know she’ll always be equal to or less than:

Soon we can transform into an unambiguous and manipulate:

So we are sure that from a c of A+B+C the function c.g(n) domina f(n) for the whole of n >= 1.

Taking the 5n² + 3n by example and applying logic we are sure that a c of 8, coming from (5+3+0), is sufficient to master the function, which does not imply that there is no c lower than also dominate it!

Prove that f(n) which belongs to the set of O(g(n))

In this case we have to use the formula:

Where it will belong to the set if c is a finite real number greater than or equal to 0.

Applying to the same example, and taking f(n) as 5n² + 3n and g(n) as n² we have:

Like c is 5, proof that 5n² + 3n belongs to O(n²)

We can also generalize this proof to any quadratic function, in the form of :

Like a is a coefficient, thus a constant, automatically proves that all quadratic functions belong to O(n²) unless this is negative, which for a complexity analysis of an algorithm may not be.

Both proofs can naturally be extrapolated to functions other than quadratic, generalizing a solution to these types of functions.

Answer 2

The complexity of algorithms is given by a function. When we are dealing with classic nonrecursive problems, we usually come across polynomials.

TL;DR, the @Isac response shows in a very elegant way the necessary results

TL;DR2, optimal response with optimal mathematical rigor on the relevance of function to its order of complexity

As stated in the commentary, the large notation O sets. So when we talk about n^2 + n = O(n^2), we are saying that the function n^2 + n belongs to the set O(n^2). When we say that O(n^2) = O(n^3) we are saying that the set O(n^2) is contained in O(n^3); note that this operation is not commutative as it is not traditional equality, so despite O(n^2) = O(n^3) be true, O(n^3) = O(n^2) is false.

Okay, now how do we define the relevance of a function to a set described by large notation O? Doing a function division leading to the infinity limit (literally, I’ll come back to that point later).

You may have noticed that the big notation O is always accompanied by a function, right? How O(n log n), O(n), O(n^2), O(e^n), O(n^3 + n). The function within the parentheses represents its behavior; I haven’t found a formal name, but we can call this function set signature. the name for this function is limiting function (information courtesy of @LINQ).

To determine whether a function f(x) belongs to the set O(g(n)), we need to know if f(x) dominates the signature function limiting function of the whole g(x); if f(x) dominate g(x), then f(x) does not belong to O(g(x)), belongs to its complementary set omega(g(x)).

Notation omega: in large notation O, we define which functions have maximum asymptotic behavior equal to signing set limiter, in the rating omega, we define which functions have minimum asymptotic behavior equal to signing set; for example, Insertion Sort works in omega(n) (previously ordered set or slightly messy) but merge Sort works in omega(n log n)

Notation theta: if f(x) = O(g(x)) and f(x) = omega(g(x)), then f(x) = theta(g(x)); the notation theta establishes minimal and maximum asymptotic behaviors at the same time; for example, unbranded Bubble Sort works on theta(n^2).

So now we need to define the operation of domination between functions. I will call this function domina(f, g), it takes two functions and returns one of three possible results:

• dominada if f is dominated by g;
• co-dominantes if it is not possible to define who dominates whom;
• dominante if f dominate g.

The function domina(f,g) is described as such:

---

Okay, now we know how to define when a function f(x) belongs to a group O(g(x)), but this is still not enough to prove whether a given algorithm runs in that order of complexity. To know this, it is necessary to know more or less how many operations will be necessary for the algorithm to work.

Defining amounts of operations depends on the machine running the algorithm. For example, an x86 has as a unit operation the sum of two 16-bit numbers n and m returning another 16-bit number making a sum in O(1); a simple Turing machine using unary notation cannot sum into a constant term of operations, but would need to do O(n + m) operations to complete processing.

So, yeah, soma(n, m) = O(1) on x86 processors with n and m with a fixed size of 16 bits, but soma(n, m) = O(n + m) on a Turing machine. (Note: on the Turing machine, we are not limiting the values of n nor of m).

Normally, basic arithmetic operations (such as summation, multiplication and division) with palpable numbers are done in fixed habitation and we consider them with weight O(1).

Small informal demonstration: b is therefore constant O(1); n is limited by b digits, having size O(b); the sum using binary numbers is done by analyzing each bit of n and of m a single time, together with an auxiliary variable, so the Turing machine will pass through all the bits only once, so O(tamanho(n) + tamanho(m)); as the size is limited to O(b), O(tamanho(n) + tamanho(m)) = O(O(b) + O(b)) = O(b + b) = O(2b) = O(b) = O(1).

In nonrecursive cases (either directly or indirectly), simply check the loops to see how many operations are done. Let’s look at your case:

function somaMatriz(matA, size)
  let soma = 0;
  for(let i = 0; i < size; i++) {
    for(let j = 0; j < size; j++) {
      soma += a[i][j];
    }
  }
  return soma;
}

We can unlock that function in two and have the same asymptotic behavior:

function somaLinha(matA, size, i) {
  let soma = 0;
  for(let j = 0; j < size; j++) {
    soma += a[i][j];
  }
  return soma;
}

function somaMatriz(matA, size) {
  let soma = 0;
  for(let i = 0; i < size; i++) {
    soma += somaLinha(matA, size, i);
  }
  return soma;
}

Does that mean that somaMatriz(matA,size) will do O(size*O(somaLinha(matA,size,i)) + 2) operations; size * O(somaLinha(matA,size,i)) because the outer loop repeats size times (i of [0,size) is O(size)) doing the operation somaLinha(matA,size,i) each time. The 2 which appears is due to return and initialization, but we know that any growing function dominates a constant value, so this 2 ends up leaving the signature.

Very well, to set now the cost of somaLinha(matA,size,i) we can divide it into two parts (similarly to what we have just done with somaMatriz(matA, size)):

function operador_soma(a, b) {
  return a + b;
}

function somaLinha(matA, size, i) {
  let soma = 0;
  for(let j = 0; j < size; j++) {
    soma = operador_soma(soma, a[i][j]);
  }
  return soma;
}

Similarly, somaLinha(matA, size, i) will do O(size) operations of operador_soma. operador_soma is only a simple sum of reasonable numbers and fixed dwelling, then executes in O(1). Therefore, somaLinha(matA, size, i) = O(size * operador_soma) = O(size * O(1)) = O(size).

Replacing this result in the asymptotic behavior of somaMatriz, we have to O(simaMatriz,matA,size) = O(size*O(somaLinha(matA,size,i)) + 2) = O(size*O(O(size)) + 2) = O(size * size) = O(size ^2).

---

When the loop does not have a very 100% size defined in an obvious way, the analysis is a little more complicated.

Take as an example the function that makes the union between two ordered sets (based on the function of that answer:

entrada:
  A, conjunto ordenado de elementos do tipo E
  B, conjunto ordenado de elementos do tipo E
  cmp, função sinal que compara dois elementos de E
retorno:
  C, conjunto de elementos do tipo E oriundo da união de A e B

começo
  i <- 0 # índice para iterar em A
  j <- 0 # índice para iterar em B
  C <- []
  ultimo_elemento_adicionado <- null

  enquanto i < A.tamanho && j < B.tamanho:
    s = cmp(A[i], B[j])
    se s == '0':
      # elementos são iguais, um deles como elemento candidato
      candidato <- A[i]
      i <- i + 1
      j <- j + 1
    senão, se s == '-':
      # A[i] < B[j], então próxima comparação será com A[i + 1] e B[j]; A[i] agora é candidato
      candidato <- A[i]
      i <- i + 1
    senão # caso trivial onde s == '+':
      # A[i] > B[j], então próxima comparação será com A[i] e B[j + 1]; B[j] agora é candidato
      candidato <- B[j]
      j <- j + 1
    # agora vamos ver se o candidato deve ser inserido em C: precisa ser distinto do último elemento adicionado, ou ser o primeiro elemento adicionado
    se ultimo_elemento_adicionado != null && cmp(candidato, ultimo_elemento_adicionado) != '0':
        ultimo_elemento_adicionado = candidato
        C.push(candidato)
  # caso i ou j extrapolem o tamanho de A ou B, respectivamente, não há mais comparações a se fazer
  retorna C
fim

Whereas the operations of cmp are performed in constant time O(1) and that adding an element at the end of an indexed set is also done in O(1).

The stopping condition is when i reaches the size of A or when j reaches the size of B. For loop iteration, we obtain that i or j (or inclusive) are increased. This means that, to stop by the condition of i >= A.tamanho, will be necessary A.tamanho increment operations in i; meanwhile, to stop by the condition of j >= B.tamanho, will be necessary B.tamanho increment operations in j. As each iteration I ensure there is at least one increment, the maximum iterations made is (A.tamanho - 1) + (B.tamanho - 1) + 1, so this bond needs O(A.tamanho + B.tamanho) operations to be executed.

---

In the case of merge Sort, we have a recursive function. Your analysis is even more complicated, so I won’t worry about her formalism, but about passing on the general idea.

Reviewing the merge Sort:

mergeSort(E[] entradaDesordenada, E[] areaTrabalho, int ini, int end) {
    if (end - ini <= 1) {
        return;
    }

    int middle = (ini + end) / 2;
    mergeSort(areaTrabalho, entradaDesordenada, ini, middle);
    mergeSort(areaTrabalho, entradaDesordenada, middle, end);
    merge(entradaDesordenada, areaTrabalho, ini, middle, end);
}

The idea of merge is to join two ordered sets into a third ordered set. The bulk of the algorithm is very similar to the union algorithm I presented earlier, including the same behavior. Therefore, merge(A) = O(tamanho(A)); if we call tamanho(A) = n, we have to the complexity of merge = O(n).

So all that remains is to define how many times merge will be called. A recursion mergeSort is made so that, in recursive call, only half of the elements are passed. So the depth of recursive calls is log2(n); as log2(n) = log(n) * log2(10), we can say that the depth is O(log n). For each recursion level, mergeSort will be called twice, each call with n/2 elements; then each level will call merge for n/2 elements 2 times.

The general idea can be seen in this image:

Note that in each level we run several times the merge (an execution for each node of the tree). In all, the amount of merging elements, at the same level of recursion depth, is n. So on the whole we have to be done O(profundidade da recursão * n) operations. As the depth is O(log n), the quantity of operations is O(n log n).

---

What is the relevance of this in practical life? Well, I did an experiment to answer a question about sorting algorithm performance. You can check the results in response. The difference between a time complexity algorithm O(n log n) and O(n^2) up to two orders of magnitude in total time for an input with n=100.000

Answer 3

The notation Θ

The question is always to verify what is the term of the equation that dominates. For this, we use the notation (reads "Téta").

A function belongs to a class if, and only if:

That is, the function belongs to a class if, and only if, from a given value , the result of is always greater than or equal to the value of mutilated by some constant greater than zero and less than or equal to the value of mutilated by some other constant greater than .

For example, be . We have to because for all the value of , we find that . In this case, we have to . To prove it, we can look at the table:

╔═══╦═════╦══════════╦═════╗
║ n ║ 5n² ║ 5n² + 3n ║ 6n² ║
╠═══╬═════╬══════════╬═════╣
║ 1 ║   5 ║        8 ║   6 ║
║ 2 ║  20 ║       26 ║  24 ║
║ 3 ║  45 ║       54 ║  54 ║
║ 4 ║  80 ║       92 ║  96 ║
║ 5 ║ 125 ║      140 ║ 150 ║
║ 6 ║ 180 ║      198 ║ 216 ║
╚═══╩═════╩══════════╩═════╝

In this table we see that for all , the value of is between the value of and of . This shows that .

How can we find the values of , and ? Any numbers and such that would serve. The 5 is the coefficient of the term of higher degree. We could use to and any values satisfying that inequality, such as 5 and 5,0001, 3 and 10, 0,0001 and 10000. But what I did was choose the coefficient of the term of higher degree (5) for the and add 1 to it to get the . With this we can calculate the as follows:

The general formula is this:

Obviously this depends on the choice of the value of .

But so far, we have assumed that we already knew the class was . Suppose we tried with other classes:

╔═════╦══════════╦══════╦════════╗
║   n ║ 5n² + 3n ║ 6n   ║  1000n ║
╠═════╬══════════╬══════╬════════╣
║   1 ║        8 ║    6 ║   1000 ║
║   2 ║       26 ║   12 ║   2000 ║
║   3 ║       54 ║   18 ║   3000 ║
║   4 ║       92 ║   24 ║   4000 ║
║   5 ║      140 ║   30 ║   5000 ║
║   6 ║      198 ║   36 ║   6000 ║
║ ... ║      ... ║  ... ║    ... ║
║ 199 ║   198602 ║ 1194 ║ 199000 ║
║ 200 ║   200600 ║ 1200 ║ 200000 ║
║ 201 ║   202608 ║ 1206 ║ 201000 ║
╚═════╩══════════╩══════╩════════╝

Note that the value of always goes beyond the . Even if we use a huge coefficient and do , we have to for any values of , the value of is bigger. This means that exceeds the value of any linear function (even if the coefficient used is very large), given a value of large enough.

On the other hand, if we try with a higher degree function:

╔══════╦═══════════╦═══════════════╗
║    n ║  5n² + 3n ║       0.001n³ ║
╠══════╬═══════════╬═══════════════╣
║    1 ║         8 ║         0.001 ║
║    2 ║        26 ║         0.008 ║
║    3 ║        54 ║         0.027 ║
║    4 ║        92 ║         0.064 ║
║    5 ║       140 ║         0.125 ║
║    6 ║       198 ║         0.216 ║
║  ... ║       ... ║           ... ║
║ 5000 ║ 125015000 ║ 125000000.000 ║
║ 5001 ║ 125065008 ║ 125075015.001 ║
╚══════╩═══════════╩═══════════════╝

We have the opposite of the previous case, for any values of , the value of is smaller. This means that has its value exceeded by any cubic function (even if the coefficient used is very small), given a value of large enough.

As you may have noticed, lower grade terms and coefficients matter little in the end. If the class has been chosen for any function such that , then any coefficients and appropriate terms used will serve and the lesser terms will become irrelevant. If the class chosen is inadequate, then there will be no terms and which satisfy the equation of of the beginning of this answer.

With this, we have that all quadratic functions are in the class . All linears are in the class . All cubics are in class . All logarithms are in the class . All exponentials are in the class .

In general classes follow a hierarchy similar to this:

These are the most common complexity classes.

What about the "asymptotic"?

Asymptotic behavior means the behavior of a function tending to infinity. That is, if we consider with a very large value. As already demonstrated above, when this occurs, the terms of lesser degree become negligible.

What about O and Ω?

Let’s go over the equation of :

Let’s focus on that part:

This could be divided into two inequalities:

And then we’d have this:

And as a consequence:

The notation (reads "oh great") is very popular, more popular than the inclusive. The represents the upper limit of a function, but this limit does not need to be exact. That is, it is something that the function never exceeds given a value of big enough. So, if you have any function such that , then you could say that is quadratic or lower.

Already the (reads "big omega") is the lower limit (that is, something that is never exceeded down), which also does not need to be exact. So if you have any function such that , then you could say that is quadratic or higher.

When the upper and lower limit coincide (even with different coefficients), then we have the . So if you have any function such that , then you could say that is quadratic, no more and no less. You could also say that and at the same time.

That is, if , we have to:

 |   | 
 |   | 
 |   | 

What about o and Ω?

Whereas the indicates an upper limit for the function, the (read "O little one") represents what is beyond that limit. Likewise, the represents the lower limit, while (read "small omega") represents what is below that limit. Soon:

 | 
 | 
 | 

This is because , which is quadratic, is beyond linear, so . But it is below the cubic, and therefore .

Notation with =

Often you see people using instead of . Strictly speaking this is an abuse of the notation of "=", but it is a common abuse that everyone does, including in highly regarded academic articles. The right thing would be to use the since the represents the set of functions that are quadratic and what is being observed is not equality between sets but the belonging of a function to a given set of functions.