# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,458 questions
Filter by
Sorted by
Tagged with
35k 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 ...
• 1,323
29k views

### Solving or approximating recurrence relations for sequences of numbers

In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested ...
• 72.6k
7k views

### Are there any problems that get easier as they increase in size?

This may be a ridiculous question, but is it possible to have a problem that actually gets easier as the inputs grow in size? I doubt any practical problems are like this, but maybe we can invent a ...
• 923
8k views

### How is this sorting algorithm Θ(n³) and not Θ(n²), worst-case?

I just starting taking a course on Data Structures and Algorithms and my teaching assistant gave us the following pseudo-code for sorting an array of integers: ...
7k 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))$. ...
• 1,642
72k views

### How do O and Ω relate to worst and best case?

Today we discussed in a lecture a very simple algorithm for finding an element in a sorted array using binary search. We were asked to determine its asymptotic complexity for an array of $n$ elements. ...
• 1,045
11k views

### O(·) is not a function, so how can a function be equal to it?

I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$. I understand semantics of it. But $T(n)$ ...
• 591
20k views

• 251
6k views

### Is O((n^2)*log(n)) greater than O(n^(2.5))?

I know that $O(n^2\times \log(n))$ is greater than $O(n^2)$, but is $O(n^2\times \log(n))$ greater than $O(n^{2.5})$?
1k views

### What goes wrong with sums of Landau terms?

I wrote $\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n)$ but my friend says this is wrong. From the TCS cheat sheet I know that the sum is also ...
• 72.6k
10k views

### Is "super-exponential" a precise definition of algorithmic complexity?

I cannot seem to find a precise definition of what "super-exponential" is supposed to refer to when one's talking about an algorithm's time complexity. For instance, if an algorithm runs for $nC(n-1)$...
• 243
948 views

### Do non-computable functions grow asymptotically larger?

I read about busy beaver numbers and how they grow asymptotically larger than any computable function. Why is this so? Is it because of the busy beaver function's non-computability? If so, then do all ...
• 527
32k views

### What does it mean by saying "Asymptotically more efficient"?

What does it mean when we say that an algorithm $X$ is asymptotically more efficient than $Y$ ? $X$ will be a better choice for all inputs. $X$ will be a better choice for all inputs except small ...
• 472
2k views

### Algorithms with O(sqrt(N)) SPACE complexity?

Are there any known algorithms for formulated problems that require a SPACE complexity of O(sqrt(N))? I know that algorithms with that big-O time complexity exist.
• 131
3k 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 ...
• 133
6k views

### Does it make sense to say Big Theta of 1? Or should we just use Big O?

Does saying $f(x) = \Theta(1)$ provide any extra information over saying $f(x) = O(1)$? Intuitively, nothing grows more slowly than a constant, so there should be no extra information in specifying ...
• 249
573 views

### Infinite chain of big $O's$

First, let me write the definition of big $O$ just to make things explicit. $f(n)\in O(g(n))\iff \exists c, n_0\gt 0$ such that $0\le f(n)\le cg(n), \forall n\ge n_0$ Let's say we have a finite ...
• 3,708
3k views

### Simplify complexity of n multichoose k

I have a recursive algorithm with time complexity equivalent to choosing k elements from n with repetition, and I was wondering whether I could get a more simplified big-O expression. In my case, $k$ ...
• 245
12k views

### What is an Efficient Algorithm?

From the point of view of asymptotic behavior, what is considered an "efficient" algorithm? What is the standard / reason for drawing the line at that point? Personally, I would think that anything ...
• 2,921
715 views

317 views

• 213
793 views

### Error in the use of asymptotic notation

I'm trying to understand what is wrong with the following proof of the following recurrence $$T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n$$  T(n) \leq 2\left(c\left\...
• 373
1k views