64 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 ...
67 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 ...
98 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.
120 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, ...
511 views

94 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$ ...
6k 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$. ...
3k 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))$. ...
25k 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 ...