# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,032 questions
Filter by
Sorted by
Tagged with
31 views

### Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not?

I am having difficulties in understanding why the recurrence $$T(n)=3T(n/4) + n\log n$$ is solvable with Master Method but $$T(n)=2T(n/2) + n\log n$$ isn't? Despite they both look very similar ...
227 views

### Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?

I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in ...
26 views

### Big-O notation for the given function whose runtime complexity grows faster than the input

I struggle to determine the runtime complexity of a function I thought of while trying to solve this quiz. The quiz itself goes like this: Write a program to find the n-th ugly number. Ugly numbers ...
31 views

### Simplify the asymptotic expressions $O(n^2 + n) + \Omega (n^2 + n \log n)$

How can it be shown that the expression $O(n^2 + n) + \Omega (n^2 + n \log n)$ simplifies to $\Omega (n^2)$? Why is it not $\Theta(n^2)$?
159 views

### Is $n^{1/\log \log n} = O(1)$?

Is $n^{1/\log \log n} = O(1)$ ? Suppose that $n^{1/\log \log n} = c$ where $c$ is constant. Taking logs of both sides, $$\frac{1}{\log \log n}\log n = \log c.$$ I am not able to spot an error. ...
24 views

### In Big-O notation, what does it mean for T(n) to be upper bounded by something

I do not have much experience in mathematics but I would really like to grasp Big-O notation on its mathematical level. I already read What does the "big O complexity" of a function mean? ...
215 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})$?
65 views

### Quickly obtaining sums of sets of numbers

We are given a set of $n$ bits, call them $a_1$, $a_2$,...,$a_n$. We are also given a set of $m$ sums, where the sums $s_1$, $s_2$,...,$s_k$,...,$s_m$ are given as sums of some of the bits. For ...
3k views

### Justification for neglecting constant factors in Big O

Many a times if the complexities are having constants such as 3n, we neglect this constant and say O(n) and not O(3n). I am unable to understand how can we neglect such three fold change? Some thing ...
36 views

### Summation of asymptotic notation

How can we solve summation of asymptotic notations like given below: $$\sum_{k=1}^{n-1} O(n).$$
76 views

### Asymptotics of $\frac{1}{\log(\frac{2^n}{2^n-1})}$

I am trying to understand the asymptotics of $$f(n) = \frac{1}{\log(\frac{2^n}{2^n-1})}$$ In particular, is there some $c \geq 1$ such that $f(n) = O(n^c)$?
23 views

### The space complexity of a function that allocates space based on the input value and not size

What is the space complexity of the following hyphotetical function: void function(int n) { int[] array = new int[n]; // allocate array of size n return; } ...
55 views

37 views

### Can we apply the Master Theorem to the following recurrence?

Our recurrence is $$T(n)= \begin{cases} T(\lfloor{n/2}\rfloor)+(\log(n))^{2}, & \text{if n>1} \\ 1 & \text{if n=1.} \end{cases}$$ I have identified $a = 1 > 0$, and $b = 2 > 1$...
43 views

### How to show that every quadratic, asymptotically nonnegative function $\in \Theta(n^2)$

In the book CLRS the authors say that every quadratic, asymptotically nonnegative function $f(n) = an^2 + bn + c$ is an element of $\Theta(n^2)$. Using the following definition \begin{align*} \...
40 views

### Bubble sort: how to calculate amount of comparisons and swaps

For a given sequence 1, N ,2 ,N −1 ,3, N −2, ... I want to calculate the number of comparisons and swaps for bubble sort. How can I accomplish that using $\theta ()$ notation? I would know how to do ...
26 views

### Proving that $S_1+S_2 \leq f^{-\omega(1)}$

I am trying to show for every c, there exists $M\text{ such that }(x,y,z)\geq M$ then $S_1(x,y,z) + S_2(x,y,z) \leq ( f (x,y,z))^{-c}$ . For a particular $S_1,S_2,f$. Does it suffice to prove there ...
41 views

### Solving a recurrence relation involving square roots

Give an asymptotic upper bound for $$T(n) = \sqrt{n}·T(\sqrt{n})+n+n/\log n.$$ How can I solve this recurrence relation, which involves square roots?
3k views

### Solving recurrence relation with square root

I am trying to solve the following recurrence relation :- $T(n) = T(\sqrt{n}) + n$ using masters theorem. We can substitute $n = 2 ^ m$ $T(2^m) = T(2 ^ {\frac{m}{2}}) + 2^m$ Now we can rewrite it ...
26 views

### Asymtotic bound for recurrence of $T(n)=2T(n/2)+ \sum_{i=0}^{n} (i+2)^2$ using substitution
What can be an initial guess for finding the tight asymptotic bounds of $T(n)=2T(n/2)+ \sum_{i=0}^{n} (i+2)^2$ using substitution method?