# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

993 questions
Filter by
Sorted by
Tagged with
28 views

### Does O(f(n)) + O(g(n)) = O(max{f(n), g(n)})?

A question from a lecture of mine. The way I see it, while summing sets is meaningless, O(f(n)) + O(g(n)) is obviously limited from above by the greatest function in either, which means that I ...
5k views

### DFS and BFS Time and Space complexities of 'Number of islands' on Leetcode

Here is the question description. The first 2 suggested solutions involve DFS and BFS. This question refers to the 1st two approaches: DFS and BFS. Apparently, the grid can be viewed as a graph. I ...
30 views

### How can I find $\Theta(log(m_1)+…+log(m_k))$ as related to $m$?

given: $$m_1+m_2+...+m_k=m$$ How can I find $\Theta(log(m_1)+...+log(m_k))$ as related to $m$? I know that i can doing that: $O(log(m_1)+...log(m_k))=O(log(m)+...+log(m))=O(k \cdot log(m))$ , but ...
52 views

108 views

### Definition of an Upper Bound

The definition my professor gave us is: f(n) is O(g(n) for constant c > 0 and n0 ≥ 0 where all n ≥ n0 and f(n) ≤ cg(n). I was wondering what n0 and n are? Example: for the function f(n) = an2+ bn + ...