It’s enough to say it’s not O(n2) for a basic reason, if you have two dimensions and each one can have a different size (yes, it is possible), only use one n
doesn’t make much sense.
In fact it is n
there is not so obvious according to the statement. The n
in fact is the m
times n
, where m
is the quantity of elements of a dimension and n
is the amount of elements of the other. Or we can just define that n
is the total number of elements in the matrix. So the total of elements that must evaluate complexity is O(n). This multiplication I spoke of is just a way to find the value of n
, but you can know it in some other way that gives the whole amount without making any account.
Complexity should be measured according to the total amount of elements and not the organization of that data in memory. This data structure has only n
elements.
The algorithm runs on top of this amount and each of them is evaluated only once, so the complexity is linear.
When the size of the two dimensions are equal we can say that multiplication gives the same n
times n
and because of this it is n2, but O(n2) is different from O(n2), in this case specified of the same size of the dimensions, and only in this square matrix, O(n2) == O(n).
That is why the correct is to demonstrate complexity as O(n). If O(n2) would only work for a square matrix, that is, it would depend on the input you can’t guarantee.
See that placing a counter of times that there is an evaluation gives the same amount of total elements of the matrix:
function totalSum(a) {
let total = 0;
let contador = 0;
for (const elem of a) {
for (const subElem of elem) {
total += subElem;
contador++;
}
}
console.log(contador);
return total;
}
// Exemplo de entrada:
totalSum([[1, 2], [3, 4]]); // 10
I put in the Github for future reference.
The second is an algorithm fundamentally different from the first, no matter the input (it even matters in the sense that the algorithm deals with different things, but not that the input itself makes the difference in complexity directly).
It does a little different and is a little more complicated, it usually be smaller than linear in most cases.
Now here the amount of evaluations depends on the values you find, you can calculate the complexity, but the account is not within those patterns that we use in most cases, is given by a more complex formula.
Recalling that Big O complexity measures the worst case, then we can say that the second algorithm is O(n2) since there are entries that can make it quadratic.
let contador = 0;
function allIncludes(a, b) {
let allExists = null;
for (const aElem of a) {
// Note que o `includes` abaixo irá iterar sobre cada elemento de `b` até o
// fim dos elementos, ou até que algum elemento seja igual a `aElem`.
// Uma complexidade próxima de `O(n)`.
if (includes(b, aElem)) {
// Se `exists` já for `true`, irá continuar como `true`.
// Se for `false`, não será atribuído.
if (allExists === null) {
allExists = true;
}
} else {
allExists = false;
}
}
console.log(contador);
contador = 0;
return allExists;
}
// Ignore:
function includes(arr, elem) {
for (const el of arr) {
if (el === elem) {
return true;
}
contador++;
}
return false;
}
// Exemplo de entrada:
allIncludes([1, 2, 3], [3, 2, 1]); // true
allIncludes([1, 2, 3], [1, 2, 4]); // false
I put in the Github for future reference.
I don’t know if the title of the question is the most ideal one for this case. If anyone wants to suggest a better title, I would be grateful. :)
– Luiz Felipe
Does this Answer your Question? How to improve my code performance with "for"?
– Jefferson Quesado
@Jeffersonquesado, I don’t think so. My question is not about improving the algorithm. I wondered if the arguments of a function could alter its complexity in the above examples, and not how to improve them... It turns out that the answers to the other question add a little to this question, but I do not believe that they are duplicates...
– Luiz Felipe
the problem was the author’s perception of cubic complexity of the question Inkei. His is the appearance of quadratic complexity. How do the questions differ? In my view, the answers to the question Inkei answered yours, including that of Maniero gave a deja vu when I saw above
– Jefferson Quesado