# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,056 questions
Filter by
Sorted by
Tagged with
424 views

### Common Algorithms without Asymptotically Tight Bounds

I can think of functions such as $n^2 \sin^2 n$ that don't have asymptotically tight bounds, but are there actually common algorithms in computer science that don't have asymptotically tight bounds ...
509 views

163 views

174 views

### Finding lambda of Master Theorem

Suppose I have a recurrence like $T(n)=2T(n/4)+\log(n)$ with $a=2, b=4$ and $f(n)=\log(n)$. That should be case 1 of the Master theorem because $n^{1/2}>\log(n)$. There is also a lambda in case 1: ...
696 views

### Sums of Landau terms revisited

I asked a (seed) question about sums of Landau terms before, trying to gauge the dangers of abusing asymptotics notation in arithmetics, with mixed success. Now, over here our recurrence guru JeffE ...
243 views

### asymptotic notations with two exponents

I am familiar with asymptotic notations like Big-O ,little-o. But while I am reading some papers people are using the notations like $O(\epsilon^{1/2^d})$, $O(d)^d$ etc. I couldn't understand these ...
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?
120 views

### Height of AVL after entries

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 ...
146 views

3k views

### Confusion about big-O notation comparison of two functions

On page 16 of this algorithms book, it states: For example, suppose we are choosing between two algorithms for a particular computational task. One takes $f_1(n) = n^2$ steps, while the other takes ...
1k views

### How asymptotically bad is naive shuffling?

It's well-known that this 'naive' algorithm for shuffling an array by swapping each item with another randomly-chosen one doesn't work correctly: ...
2k views

111 views

299 views

### Complexity inversely propotional to $n$

Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?