Examples of algorithms that have runtime O(N + M) resp O(NM)

Question

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

Answer 1

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(n\log m)$. (We don't need to worry about the base of the logarithm, since $\log_a m = k\log_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.