N
N
NameOf Var2017-06-15 01:29:04
Algorithms
NameOf Var, 2017-06-15 01:29:04

How to properly estimate the time complexity of an algorithm?

Let there be a main function main (with which the program starts). In this function, the func1() and func2() functions are called sequentially. The func1() function is implemented like this:

void func1()
{
     ...
     for (int i = 0; i < n; i++)
          for (int j = 0; j < m; j++)
               { ... }
     ....
}

Those. the time complexity will be N*M.
The func2() function is also implemented, but it depends on other input parameters, i.e.
void func2()
{
     ...
     for (int i = 0; i < k; i++)
          for (int j = 0; j < l; j++)
               { ... }
     ....
}

Those. the time complexity in this case is K*L.
Question: what will be the overall complexity of the algorithm as a whole (i.e. the time complexity of the main function)? Is it correct to say that in this case the complexity of the algorithm will be N*M + K*L?

Answer the question

In order to leave comments, you need to log in

3 answer(s)
M
Mercury13, 2017-06-15
@hax

In general, yes. But sometimes such estimates can be simplified. And simplifications can be made on two counts:
1. More accurate estimates. In this case, I can't think of one.
2. Simpler estimates: after all, an estimate is the Landau symbol O(f(·)), which is up to a constant. If, for example, K<N and L<M, then the complexity will be just N·M.

A
Andryukha, 2017-06-15
@syrov

Probably mat expectation E[KL], that if they (K and L) are independent then E[K]E[L]

T
tomatho, 2017-06-15
@tomatho

It all depends on what's in the brackets. If there are any conditions or cycles, then it may turn out to be:
And this is far from uncommon when there are three cycles, and the complexity seems to be only two cycles.
The simplest example is breadth-first search (bfs). It loops over the vertices, which loops over the edges of the vertex, that is, in the worst case, it turns out O (N * M) where N is the number of vertices, and M is the number of edges, but obviously this is just O (N + M ), but I wanted to emphasize that this is due to the fact that in this algorithm each edge is traversed a maximum of two times: O(2M) = O(M), and each vertex is traversed a maximum of once O(N).

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question