Linked Questions
14 questions linked to/from Is O(mn) considered "linear" or "quadratic" growth?
1
vote
1
answer
2k
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 ...
- 111
101
votes
3
answers
35k
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 ...
- 1,323
54
votes
4
answers
7k
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))$. ...
- 1,692
20
votes
1
answer
16k
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 ...
- 423
2
votes
3
answers
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 ...
- 43
4
votes
1
answer
4k
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$.
...
- 143
2
votes
1
answer
3k
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)...
- 33
1
vote
2
answers
137
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$ ...
- 418
3
votes
2
answers
237
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{...
- 133
2
votes
2
answers
137
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.
- 157
1
vote
2
answers
129
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, ...
- 519
2
votes
1
answer
87
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 ...
- 121
1
vote
1
answer
87
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 ...
- 113
2
votes
1
answer
75
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 ...
- 151