# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,267 questions
Filter by
Sorted by
Tagged with
0answers
24 views

### In Hashing-collison resolved by chaining: Intuition behind $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$

Hashing-collison resolved by chaining: $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$ I was going through the text Introduction to Algorithms by Cormen et. al. and in the ...
0answers
50 views

### Big $O$ approximation for $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$

I have the following complexity equation: $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$ with the base case $T(m)=1$. Is it possible to calculate a big $O$ approximation for such equation? What is the right ...
1answer
29 views

### Intuition of lower bound for finding the minimum of $n$ (distinct) elements is $n-1$ as dealt with in CLRS

I was going through the text Introduction to Algorithms by Cormen et. al. where there was a discussion regarding the fact that finding the minimum of a set of $n$ (distinct) elements with $n-1$ ...
1answer
3k views

### When is a bound asymptotically tight?

What does it mean that the bound $2n^2 = O(n^2)$ is asymptotically tight while $2n = O(n^2)$ is not? We use the o-notation to denote an upper bound that is not asymptotically tight. The deﬁnitions of ...
1answer
16 views

### Is it correct or incorrect to say that an input say $C$ causes an average run-time of an algorithm?

I was going through the text Introduction to Algorithm by Cormen et. al. where I came across an excerpt which I felt required a bit of clarification. Now as far as I have learned that that while the ...
1answer
51 views

### Clarifying $\sum_{h=0}^{\lfloor lg(n)\rfloor}\lceil\frac{n}{2^{h+1}}\rceil O(h)=O(n\sum_{h=0}^{\lfloor lg(n)\rfloor}\frac{h}{2^h})$ in BUILD-MAX-HEAP

I was going the text Introduction to Algorithms by Cormen et. al. Where I came across a step in the analysis of the time complexity of the $BUILD-MAX-HEAP$ procedure. The procedure is as follows: <...
1answer
34 views

### Clarifying statements involving asymptotic notations in soln of $T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$ using recursion tree and substitution

Below is a problem worked out in the Introduction to Algorithms by Cormen et. al. (I am not having problem with the proof but only I want to clarify the meaning conveyed by few statements in the text ...
1answer
62 views

1answer
90 views

### Time complexity of code running at most summation(N) times in a loop

Let’s say I have a JavaScript loop iterating over input of size N. Let’s say all elements in N are unique, so the includes method traverses the entire output array on each loop iteration: ...
1answer
62 views

1answer
245 views

### Asymptotic complexity of Combination sum problem vs Coin change problem

I've been looking at the following combination sum problem: ...
1answer
49 views

### Does the product of two functions equal the product of their Big-O's?

let's say $f(n) = O(g(n))$ and $l(n) = O(m(n))$ is it always true that $f(n) \cdot l(n) = O(g(n)) \cdot O(m(n))$ ?
2answers
74 views

1answer
2k views

### Meaning of polynomially larger or smaller in the context of the master method

I'm studying the master method of solving recurrences and I have a somewhat decent math background but I'm having difficulty understanding the concept of $n^{\log_ba}$ being polynomially smaller or ...
1answer
122 views

### Using substitution method to prove asymptotic lower bound of $T(n) = T(n-1) + \Theta (n)$

I try to prove that the asymptotics of the recurrence $T(n) = T(n-1) + \Theta (n)$ is $T(n) = \Theta(n^2)$. By $\Theta$, I mean tight bound from above and below. I can write the equation like ...
2answers
55 views

### Algorithms: Determining Asymptotic Notation from a given execution time

I'm studying for an Algorithms and Data Structure test. There is a type of question that is usually always asked by my professor but I don't know how to answer/solve it. Question 1: An Algorithm with ...
1answer
136 views

1answer
47 views

### For $T(n) = 16(T/4) + n^2\lg^3n$ prove: $T(n) = \Theta(n^2\lg^3n)$

Define: $\lg x = \log_2x$. Let $f(n), g(n)$ be some non-negative functions. Define $f(n) = \Theta (g(n))$ if $$\exists c_1,c_2 \in R\colon 0 < c_1g(n) \leq f(n) \leq c_2g(n)$$ I want ...
0answers
33 views

### Big O notation of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$

What is the O-notation (or $\Theta$ notation ) of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$ ? Can I use Sterling approximation : $n! = \Theta(\sqrt{n}\left(\frac{n}{e}\right)^n)$ ...
1answer
51 views

1answer
36 views

### Growth of exponential functions according to the big O notation

I'm preparing for an exam and trying to make some sense of the growth of the different exponential functions. I picked the trickiest functions for myself and tried to sort them according to the big O ...