21 questions linked to/from What is the meaning of $O(m+n)$?
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.
32 views

### Why is max{n,k}= Ө(n+k) [duplicate]

I saw this relationship in my exercise. max{n,k}= Ө(n+k) Could somebody prove it?
29k 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 ...
15k views

### Is O(mn) considered “linear” or “quadratic” growth?

If I have some function whose time complexity is O(mn), where m and n are the sizes of its two inputs, would we call its time complexity "linear" (since it's linear in both m and n) or "quadratic" (...
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 ...
2k views

### Asymptotic Analysis for two variables?

How is asymptotic analysis (big o, little o, big theta, big theta etc.) defined for functions with multiple variables? I know that the Wikipedia article has a section on it, but it uses a lot of ...
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$. ...
210 views

### Is $O(N+M)$ exponential or polynomial?

So In a review section, our professor asked: Given integers $N$ and $M$ Is $O(N+M)$ exponential or polynomial. It's exponential, but I just don't see how that is. I would have thought it's linear.
1k 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 ...
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 99 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$... 1answer 177 views ### What's the formal definition of Big-O notation for functions of more than one variable? For functions of a single totally ordered variable, I already know that$f(n)$is$O(g(n))$if and only if$\exists m. \exists c. \forall n. (n \ge m) \rightarrow [ f(n) \le c \cdot g(n) ]$. What I ... 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 137 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 first learned about the Big O notation in an intro to Algorithms class. He showed us that function $g \in O(f(n))$ Afterwords in Discrete Math another Professor, without knowing of the first, told ...