# Questions tagged [asymptotics]

The tag has no usage guidance.

21 questions
52 views

### How can we solve the recurrence $T(n) = T(n/2) + log^2(n)$ [on hold]

I am trying to solve the following recurrence: $T(n) = T(n/2) + log^2(n)$ So far I have come up with the following expression $T(n) = \sum^{log(n)}_0 2^klog(n/2^k)$ I cannot figure out a way to ...
58 views

### Which one of the following is the correct asymptotic notation? [closed]

While studying the complexity theory, I encountered a question which is as follows:- Which one of the following is correct? 1) θ(g(n)) = O(g(n)) ∩ Ω(g(n)) 2) θ(g(n)) = O(g(n)) ∪ Ω(g(n)) I know ...
95 views

### Growth of random square lattice trees

Consider the problem of growing a random tree on a $L\times L$ square lattice of initially disconnected vertices, starting from an isolated vertex on one of the corners of the lattice and proceeding ...
129 views

### What does “hold uniformly” mean in the context of asymptotic analysis?

What does "hold uniformly" mean in the statement of Theorem 1.7 in A Faster Subquadratic Algorithm for Finding Outlier Correlations? Here's the theorem text ("hold uniformly" is in the last line):
75 views

### Computing 'Robustness of Magic' of $n$-bit W states

Question What is the asymptotic robustness-of-magic of a $W$ state over $n$ qubits. Is it $\Theta(n)$? $\Omega(\sqrt{n})$? $O\left(\frac{n}{\lg n} \right)$? Background $W$ states are entangled ...
86 views

315 views

### the confusion about 'with high probability (w.h.p.)'

w.h.p. can often be seen in the analysis of randomized algorithms. It's definition can be seen here https://en.wikipedia.org/wiki/With_high_probability. However my confusion is that: Assuming we ...
143 views

### Preferable way to express $O(n2^n)$

Is it preferable to write $O(n2^n)$ or $O((2 + \epsilon)^n)$? If neither, what is the best way? Since I see a lot of papers with $O(1.42^n)$ instead of $O(2^{\frac{n}{2}})$ and similar transformations,...
125 views

### Using master theorem when there is a constant in the recursive term [closed]

Is it possible to use the master theorem to find the asymptotic growth of a function of the form: $$T(n) = aT(\frac{n}{b}+c)+f(n)$$ Where $c$ is a constant. Can we safely ignore this constant and use ...
235 views

### Sieve Methods for Twin Primes - How to extract algorithm from formula

I am reading Cojocaru and Murty's Introduction to Sieve Methods and their Applications. They wait until Chapter 5 to discuss the Sieve of Eratosthenes for finding primes - and their version of it is ...
65 views

### Complexity of generically inverting a class of near linear monotonic functions

Given a monotonic increasing function $f(\mathbb{N}) \rightarrow \mathbb{N}$ and a slack function $a(\mathbb{N})\rightarrow \mathbb{N}$, where $f(n) = n \pm O(a(n))$; how many calls to $f$ do we ...
### $O(m+n)$ really necessary for graph algorithms?
It is standard to express the running time of linear-time graph algorithms as $O(m+n)$ (such as depth-first-search, etc.). For nearly all such algorithms, vertices of degree zero have no effect on ...