# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

989 questions
Filter by
Sorted by
Tagged with
14k views

### Why is there the regularity condition in the master theorem?

I have been reading Introduction to Algorithms by Cormen et al. and I'm reading the statement of the Master theorem starting on page 73. In case 3 there is also a regularity condition that needs to be ...
861 views

### Definition of $\Theta$ for negative functions

I'm working out of the 3rd edition CLRS Algorithms textbook and in Chapter 3 a discussion begins about asymptotic notation which starts with $\Theta$ notation. I understood the beginning definition of:...
97 views

### Why bound of linear function is same as that of quadratic equation

I am learning algorithms. So, I came along with something very interesting. The asymptotic bound of linear function $an+b$ is $O(n^2)$ for all $a>0$. This is same as for $an^2 + bn + c$. But ...
4k views

### The order of growth analysis for simple loop

What would the order of growth for this loop be: int sum = 0; for (int n = N; n > 0; n /= 2) for(int i = 0; i < n; i++) sum++; The first loop ...
2k views

### Subtracting lower-order term to prove subtitution method works

Substation method fails to prove that $T(n)=\Theta(n^2)$ for the recursion $T(n)=4T(n/2) + n^2$, since you end up with $T(n) < cn^2 \leq cn^2 + n^2$. I don't understand how to subtract off lower-...
218 views

### Doubt with a problem of grown functions and recursion tree

I'm confused to conclude the recursion tree method a guess for the next recurrence: $$T(n)=3T\left (\left\lfloor \frac{n}{2}\right \rfloor\right) +n$$ I write some costs for the levels of tree, you ...
2k views

### Finding the number of leaves in a imbalanced recursion tree

I'm going through the MIT Online Course Videos on Intro. to Algorithms at here at around 38:00. So we have a recursion formula $\qquad T(n) = T(n/10) + T(9n/10) + O(n)$ If we build a recursion tree ...
9k views

### Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem

Introduction to Algorithms, 3rd edition (p.95) has an example of how to solve the recurrence $$\displaystyle T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log(n)$$ by applying the Master Theorem. I am ...
296 views

### Complexity inversely propotional to $n$

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

### Changing variables in recurrence relations

Currently, I am self-studying Intro to Algorithms (CLRS) and there is one particular method they outline in the book to solve recurrence relations. The following method can be illustrated with this ...
646 views

273 views

### what is the complexity of recurrence relation?

what is the complexity of below relation $T(n) = 2*T(\sqrt n) + \log n$ and $T(2) = 1$ Is it $\Theta (\log n * \log \log n)$ ?
258 views

3k 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))$. ...
861 views

3k views

### Are the functions always asymptotically comparable?

When we compare the complexity of two algorithms, it is usually the case that either $f(n) = O(g(n))$ or $g(n) = O(f(n))$ (possibly both), where $f$ and $g$ are the running times (for example) of the ...
384 views

### Recursion for runtime of divide and conquer algorithms

A divide and conquer algorithm's work at a specific level can be simplified into the equation: $\qquad \displaystyle O\left(n^d\right) \cdot \left(\frac{a}{b^d}\right)^k$ where $n$ is the size of ...
5k views

### Solving Recurrence Equations containing two Recursion Calls

I am trying to find a $\Theta$ bound for the following recurrence equation: $$T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 5n + 42$$ I figure Master Theorem is inappropriate due to differing amount of ...
696 views

### Master theorem and constants independent of $n$

I applied the Master theorem to a recurrence for a running time I encountered (this is a simplified version): $$T(n)=4T(n/2)+O(r)$$ $r$ is independent of $n$. Case 1 of the Master theorem applies ...
1k views

### Solving Recurrence Relations 'Chip & Conquer'

I've been tasked with solving some recurrence relations, and I've been running into trouble with so called 'chip & conquer' relations. Here are some example problems: $$T(n) = T(n-5) + cn^2$$ ...
451 views

### $\log^*(n)$ runtime analysis

So I know that $\log^*$ means iterated logarithm, so $\log^*(3)$ = $(\log\log\log\log...)$ until $n \leq 1$. I'm trying to solve the following: is $\log^*(2^{2^n})$ little $o$, little $\omega$, ...
1k views