Linked Questions
14 questions linked to/from Is O(mn) considered "linear" or "quadratic" growth?
95
votes
3answers
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 ...
47
votes
4answers
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))$. ...
14
votes
1answer
9k views
Can a Big-Oh time complexity contain more than one variable?
Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct ...
4
votes
1answer
3k views
Time complexity based on two variables
Suppose we have a function based on two inputs of length $m,n$. Therefore the time complexity of the function is calculated by $T(m,n)$. Suppose that we have:
$T(m,c)\in O(m^2)$ for any constant $c$.
...
3
votes
2answers
127 views
Compare Complexity of Graph Algorithm
Assume I know that there is an algorithm of complexity
$ \mathcal{O}( log ( \vert V \vert^2 \vert E \vert ) ) $
for a Graph $G(E,V)$.
How do I compare this for example to the complexity of
$ \mathcal{...
2
votes
3answers
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 ...
2
votes
1answer
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 ...
2
votes
2answers
110 views
What does it mean to add up O-terms with different variables? [duplicate]
Is this true? O(n) + O(k) =O(n+k).I have searched for it ,the answers were quite ambiguous and I couldn't find a good explanation.
2
votes
1answer
71 views
Interpretation of an asymptotic notation
Assume that we measure the complexity of an algorithm (for some problem) by two parameters $n$ and $m$ (where $m \le n$). What is the formal interpretation of the following claim: there is no ...
2
votes
1answer
1k views
$O(n+nm) = O(nm) = O(m+nm)$?
I am thinking about the worst-case space complexity of an algorithm.
Obviously, if $f \in O(nm)$ then $f \in O(n+nm)$. But is the converse true?
$O(m)+O(nm) = O(m+nm) = O(m(1+n)) = O(m)O(1+n) = O(m)...
1
vote
2answers
96 views
Simplifying an upper O-bound in two variables
I have an algorithm that depends on two input sizes n and m. The complexity breaks down to the following equation:
$\frac{nm - 1}{n-1} = O(?)$
Is Big-O of the Formula $O(mn)$ or $O(m)$ because $n$ ...
1
vote
2answers
121 views
What kind of growth is $O(0.24\cdot K\cdot 2^w)$
I've calculated the running time of an algorithm I'm interested in to be
$$O(0.24\cdot K\cdot 2^{w})\,,$$
where $K$ and $w$ are both variables. ($K$ is the number of elements in some set, ...
1
vote
1answer
72 views
Can the following O(…) expression be simplified?
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 ...
0
votes
1answer
930 views
Complexity of an algorithm with multiple inputs [duplicate]
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 ...