[Solved]: Examples of algorithms that have runtime O(N + M) resp O(NM)

ignougroup
Problem Detail: I’m looking for examples of loops that have running time $O(nm)$, $O(n+m)$ and $O(nlog m)$ to help me understand these concepts. Could anybody give some examples and explain why they have the given running time?

Asked By : om471987

Answered By : David Richerby

The following fragment sets t to a value that is $O(nm)$ (actually, it’s equal to $mn$). the outer loop executes $n$ times and, each of those times, the inner loop executes $m$ times. 

t = 0; for i=1 to n do     for j=1 to m do         t = t+1;

The following fragment runs the first loop $n$ times and then runs the second loop $m$ more times, for a total of $n+m$ (which is a trivial example of $O(n+m)$). 

t = 0; for i = 1 to n do     t = t+1; for i = 1 to m do     t = t+1;

Finally, this fragment runs the outer loop $n$ times. Each time, p is set to $m$ and then halved until it reaches 1. This answers the question “How many times do I have to multiply 1 by 2 to get something bigger than $m$, which is $log_2 m$. So the value of $t$ is $O(nlog m)$. (We don’t need to worry about the base of the logarithm, since $log_a m = klog_b m$ for some constant $k$, which all gets lost in the $O(-)$.) 

t = 0; for i = 1 to n do     p = m;     while (p > 1) do         p = p/2;         t = t+1;

The code fragments here are similar to the ones that appeared in the original version of the question. I removed them from the question, since questions that contain answers aren’t well-suited to this site.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22611