# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,118 questions
Filter by
Sorted by
Tagged with
28 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; } ...
72 views

46 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$...
49 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*} \...
179 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 ...
50 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?
47 views

### Find function that satisfy the relation

Can you find the function that satisfy the relation? $$f(n) = \Theta(g(n)), f(n) = o(g(n))$$
48 views

19 views

### When the data size and processor speed are both multiplied by 10, then a linearithmic algorithm takes double the time to finish?

Robert Sedgewick mentioned, if a computer can handle 10x data and the processor is also 10x as fast, then a $O(n^2)$ algorithm actually runs slower than before. Is this the correct idea when a ...
108 views

### O(1) distinct elements in an array implies?

Could someone explain the following question - Given the following statement viz. Consider an input array a[1..n] of arbitrary numbers. It is given that the array has only O(1) distinct elements. ...
209 views

### Basic Theta-notation question

Let $T$ be a function. Is it true that if $\exists f\forall n,m> 0.\\ \frac m {f(n)} \leq T(n,m)\leq m$ Then $\exists g.T(n,m)=\Theta(m\cdot g(n))$? In words: is such a case, is there a function ...
614 views

### What does $|V|=O(|E|)$ mean?

I was reading about Dijkstra's algorithm from this Stanford University lecture presentation. On page 18 it says Dijkstra's algorithm is $O(|V|\log|V|+|E|\log|V|)$ and I understand why. But then it ...
Given a recurrence of the form $\forall n,m.\ \ T(n,m)=\begin{cases}1,&,m=1\\\sum_i{T(n_i,m_i)}&,\text{else}\end{cases}$ Note: both $n_i$ and $m_i$ are dependent on $n,m$ so they should have ...