CODEWITHSUNDEEP
time-complexity
polmonroig
polmonroig

Reputation: 1017

Calculate function time complexity

I am trying to calculate the time complexity of this function

Code

int Almacen::poner_items(id_sala s, id_producto p, int cantidad){
it_prod r = productos.find(p);
if(r != productos.end()) {
    int n = salas[s - 1].size();
    int m = salas[s - 1][0].size();
    for(int i = n - 1; i >= 0 && cantidad > 0; --i) {
        for(int j = 0; j < m && cantidad > 0; ++j) {
            if(salas[s - 1][i][j] == "NULL") {
                salas[s - 1][i][j] = p;
                r->second += 1;
                --cantidad;
            }
        }
    }
}
else {
    displayError();
    return -1;
}
return cantidad;

}

the variable productos is a std::map and its find method has a time complexity of Olog(n) and other variable salas is a std::vector. I calculated the time and I found that it was log(n) + nm but am not sure if it is the correct expression or I should leave it as nm because it is the worst or if I whould use n² only.

Thanks

Upvotes: 0

Views: 294

Answers (3)

Caleth
Caleth

Reputation: 62576

let 

k = productos.size()
n = salas[s - 1].size()
m = salas[s - 1][0].size()

your algorithm is O(log(k) + nm). You need to use a distinct name for each independent variable

Now it might be the case that there is a relation between k, n, m and you can re-label with a reduced set of variables, but that is not discernible from your code, you need to know about the data.

It may also be the case that some of these terms won't grow large, in which case they are actually constants, i.e. O(1).

E.g. you may know k << n, k << m and n ~= m , which allows you describe it as O(n^2)

Upvotes: 1

kabanus
kabanus

Reputation: 25895

In general when using big O notation, you only leave the most dominant term when taking all variables to infinity.

n by itself is much larger than log n at infinity, so even without m you can (and generally should) drop the log n term, so O(nm) looks fine to me.

In non-theoretical use cases, it is sometimes important to understand the actual complexity (for non-infinite inputs), since sometimes algorithms that are slow at infinity can produce better results for shorter inputs (there are some examples where O(1) algorithms have such a terrible constant that an exponential algorithm does better in real life). quick sort is considered a practical example of an O(n^2) algorithm that often does better than it's O(n log n) counterparts.

Read about "Big O Notation" for more info.

Upvotes: 1

Martin Bonner supports Monica
Martin Bonner supports Monica

Reputation: 28987

The overall function is O(nm). Big-O notation is all about "in the limit of large values" (and ignores constant factors). "Small" overheads (like an O(log n) lookup, or even an O(n log n) sort) are ignored.

Actually, the O(n log n) sort case is a bit more complex. If you expect m to be typically the same sort of size as n, then O(nm + nlogn) == O(nm), if you expect n ≫ m, then O(nm + nlogn) == O(nlogn).

Incidentally, this is not a question about C++.

Upvotes: 1

Related Questions