# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,055 questions
Filter by
Sorted by
Tagged with
524 views

### Algorithm analysis question in growth of functions

How would I solve the following. An algorithm that is $O(n^2)$ takes 10 seconds to execute on a particular computer when n=100, how long would you expect to take it when n=500? Can anyone help me ...
3k views

### Big O notation of max?

I'm coding a few set comparisons and noting their big O's using different algorithms and set implementations. I got to one particular function and I decided that it is $O(max(n,m))$ runtime. Is that ...
915 views

### Asymptotics of the number of words in a regular language of given length

For a regular language $L$, let $c_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that ...
107 views

### Resolving this recurrence equation [duplicate]

I have this recurrence equation: $T(n) = T(n/4) + T(3n/4) + \mathcal{O}(n)$ $T(1) = 1$ I know that the result is $\mathcal{O}(n \log n)$ but i don't know how to proceed.
94 views

### Does $O(1) * o(1)$ equal a $o(1)$ function?

Say I have two functions $f(x) = O(1)$ and $g(x) = o(1)$. Let $h(x) = f(x)g(x)$. Is $h(x) = o(1)$? By definition of small-o $g(x)$ must approach 0 as $x \rightarrow \infty$, so I think yes. However, ...
2k views

2k views

### Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$?

From what I've read, Big O is the absolute worst ever amount of complexity an algorithm will be given an input. On the side, Big Omega is the best possible efficiency, i.e. lowest complexity. Can it ...
108 views

265 views

### Input to make worst case on big O not possible?

Sorry if this question is very simplistic; I'm just starting out and I'm trying to wrap my head around all this asymptotic bound stuff. When trying to find the upper bound for the worst case of a ...
1k views

### Why is $3^n = 2^{O(n)}$ true?

$3^n = 2^{O(n)}$ is apparently true. I thought that it was false though because $3^n$ grows faster than any exponential function with a base of 2. How is $3^n = 2^{O(n)}$ true?
Problem: Suppose $V$ is an AVL tree (a self-balancing binary search tree) of $n$ elements. After the insertion of $n^2$ elements, what would be its height? My idea: the height of an AVL tree is ...