2
$\begingroup$

I'm quite new to time-complexity analysis so I might have misunderstood some basic concepts but lets say we have the following function:

    function(int x, int y)
    for (int i = 0; i < x; i++)
    {}        

    for(int i = 0; i < y; i++)
    {}

From my understanding this function will for large inputs of $x$ and $y$ have two loops of linear growth. If the first loop is said to run $k$ times and the second $m$ times, will the big Oh notation be $O(k + m)$, or can the two inputs be merged into one variable of linear growth, like $n$, $O(n)$? Can $k$ and $m$, since they both have the same growth rate and (in the case of Big Oh analysis) equally large inputs be simplified into one variable or should they stay separate?

$\endgroup$
  • $\begingroup$ Note that Landau notation mostly breaks down for more than one variable; handle with care. $\endgroup$ – Raphael Apr 29 '18 at 11:05
2
$\begingroup$

There is a common misconception that the running time always have to depend on a single parameter. This misconception is strange since in graph theory, the running time of many algorithms is stated in terms of two parameters, the number of vertices and the number of edges. As an example, DFS and BFS run in time $\Theta(V+E)$. A priori, we do not know of any relation between $V$ and $E$ other than $E \leq \binom{V}{2}$, and so $\Theta(V+E)$ cannot be simplified further. Since $E = O(V^2)$, any algorithm running in time $O(V+E)$ also runs in time $O(V^2)$. If we know that the graph is connected then $E \geq V-1$, and so $\Theta(V+E)$ is the same as $\Theta(E)$. But for general graphs, we have no reason to assume any relation between $V$ and $E$.

In your case, you seem to want to assume that $k$ and $m$ have the same order of growth. This might be the case or might not be the case, depending on the application you have in mind. Only you can tell. It is possible to state the upper bound $O(k+m)$ in terms of a single variable: it is $O(n)$, where $n = \max(k,m)$ (or $n = k+m$). Whether this is helpful or not is up to you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.