770 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 ...
27k 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 ...
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))$. ...
8k 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 ...
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 ...
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$. ...
95 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$ ...
822 views

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)... 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, ... 2answers 104 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. 1answer 69 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 ... 2answers 110 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{...
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 ...
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 ...