# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,114 questions
Filter by
Sorted by
Tagged with
2k views

### Finding recurrence when Master Theorem fails

Following method is explained by my senior. I want to know whether I can use it in all cases or not. When I solve it manually, I come to same answer. $T(n)= 4T(n/2) + \frac{n^2}{\lg n}$ In above ...
3k views

### Time complexity based on two variables

Suppose we have a function based on two inputs of length $m,n$. Therefore the time complexity of the function is calculated by $T(m,n)$. Suppose that we have: $T(m,c)\in O(m^2)$ for any constant $c$. ...
2k views

### Decreasing runs of inner loop in outer loop [duplicate]

I am trying to determine the worst case runtime of this program: while n > 1 for i = 1,..,n m = log(n) n = n/2 Obviously the outer loop runs ...
2k views

### Asymptotic Properties of Functions in Complexity Analysis

When dealing with the analysis of time and space complexity of algorithms, is it safe to assume that any function which has tight bounds ( i.e. $f(n)=\Theta(g(n))$ is asymptotically positive and ...
63 views

### Show that a function belongs to grade of incline [duplicate]

This is a Data structures & Algorithms question. For instance I have the following grades of functions: $O(1), O(2^n), O(n \log n), O(e^n), O(n^3), O(n^{1/3})$ and $O(\log \log n)$ I need to ...
350 views

80 views

### How is this algorithm in these two complexities?

How is an algorithm with complexity $O(n \log n)$ also in $O(n^2)$? I'm not sure exactly what its saying here, I feel it may be something to do with the fact that big-oh is saying less than or equal ...
253 views

### Why does every member $f(n) \in \Theta(g(n))$, and $g(n)$ have to be asymptotically non-negative?

The following is an excerpt from CLRS: The definition of $g(n)$ requires that every member $f(n) \in \Theta(g(n))$ be asymptotically nonnegative, that is, that $f(n)$ be nonnegative whenever n is ...
585 views

504 views

### When does $1.00001^n$ exceed $n^{100001}$?

I have been told than $n^{1000001} = O(1.000001^n)$. If that's the case, there must be some value $n$ at which $1.000001^n$ exceeds $n^{1000001}$. However, when I consult Wolfram Alpha, I get a ...
167 views

### Two functions $g(n)$, $G(n)$ such that $g(n) = o(G(n))$ but $g(n+1) \neq o(G(n))$

The title of the question expresses what I'm looking for - this is to help me better understand the prerequisites for the Non-Deterministic Time Hierarchy Theorem For instance, the Arora-Barak book ...
4k views

### Solving the big-Oh notation for $T(n) = 2 T(n/2) + O(n)$ [duplicate]

Possible Duplicate: Solving or approximating recurrence relations for sequences of numbers I know that the solution for $T(n) = 2 T(n/2) + O(n)$ is $T(n) = O(n \log(n))$ But how do you get to ...
756 views

### Solving recurrence with logarithm squared $T(n)=2T(n/2) + n \log^2n$

$T(n)=2T(n/2) + n\log^2(n)$. If I try to substitute $m = \log(n)$ I end up with $T(2^m)=2 T(2^{m-1}) + 2^m\log^{2}(2^m)$. Which isn't helpful to me. Any clues? PS. hope this isn't too localized. ...
320 views

### Why is this $f(n) \leq 6n^3 + n^2 \log n \in O(n^3)$ for all $n \geq 1$?

I'm currently studying for an algorithms midterm in about 2 days and am reading from the beginning of the course, and stumbled upon this when I actually looked at the examples. The question equation: ...
93 views

### Finding $c$ and $n_0$ for a big-O bound

A book I am reading demonstrates how $5n^3 + 2n^2 + 22n + 6 = O(n^3)$, which I believe is true. After all, there exists a value $c$ for which $cn^3$ is always greater than $5n^3 + 2n^2 + 22n + 6$ for ...
161 views

170 views

### How does this recurrence relation fit the algorithm?

I have the following pseudo code: ...
1k views

15k 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 ...
1k 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:...
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 ...
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-...