4k views

### What is the meaning of $O(m+n)$?

This is a basic question, but I'm thinking that $O(m+n)$ is the same as $O(\max(m,n))$, since the larger term should dominate as we go to infinity? Also, that would be different from $O(\min(m,n))$. ...
28k views

### How does one know which notation of time complexity analysis to use?

In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity. However, there are ...
2k views

### Can we test whether two vertices are connected in time linear in the number of nodes?

Consider the problem: Given an undirected graph and two of its vertices, is there a path between them? I often read that this problem can be solved in linear time in the number of vertices! I am ...
127 views

70 views

### Does this program have a runtime of O(N) or O(n*m)

This question is similar to, but distinct from this one, in that I am considering a specific case that demonstrates an apparent inconsistency in how I see Big-O notation used. I would like to be sure ...
I have an algorithm with three variables affecting the time complexity: $k$, $L$, and $n$. I have come up with the following that expresses the complexity: $O(kn + k^2L + k^2nL + knL)$ I think I ...
I've just started reading about the complexity of algorithms, but everywhere I look, it is only defined for one input $n$. For example an algorithm is cubic if its complexity is $O(n^3)$. But what ...