# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,056 questions
Filter by
Sorted by
Tagged with
83 views

46 views

### Showing that $n\log n - n$ is $\Omega(n)$

Prove that $n\log{n} − n$ is $\Omega(n)$. I do know the answer: $\log{n} ≥ 2, \forall n \ge 4$. Thus, $n\log{n}−n\ge n ,\forall n\ge 4 \implies n \log n − n ∈ Ω(n)$. But can someone please ...
45 views

### What is the difference between Big(O) and small(o) notations in asymptotic analysis? [duplicate]

What is the difference between $O$ (big oh) and $o$ (small oh) notations in asymptotic analysis? Even though I understand that $o$ is used for a bound that is not tight, is it allowed to use $O$ ...
51 views

### Why is building a heap $\mathcal O(n)$ and not $\theta(n)$?

From what I see online, all seem to suggest that heapifying takes $\mathcal O (n)$ time, but it seems like it should always takes $\theta(n)$ time, even in the best case. Is something wrong with my ...
155 views

### Runtime complexity of a brute force factoring algorithm? (in terms of bits)

Let N be an n bit number. A brute force algorithm factors N by trying to divide N by all of the numbers between 2 and sqrt(N). Given that dividng two n bit integers takes O(n^2) time, what is the ...
54 views

96 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. ...
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 ...
207 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 ...
8k views

### How to prove any polynomial of degree $k$ is in $\Theta(n^k)$?

I want to prove that any polynomial of degree $k$ is in $\Theta(n^k)$. The coefficient of $n^k$, $a_{k}$, is positive. I know I need $0 \leq c_{1}n^k \leq a_{k}n^k + ... + a_{0} \leq c_{2}n^k$ for ...
592 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 ...
621 views

### How to find kth largest element in (max) priority queue in O(m) time?

Here is my exercise. FINDLARGEST(k): return the elements in the heap with key >=k" ... "expand the priority queue (max-heap) so that it supports FINDLARGEST(k) in O(m) time, where m is the number ...
22 views

### Useful conditions for proving super polynomial lower bound for some kind of recurrences

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 ...
To optimize my LF mapping, I was asked to do the following. Given a string, say $abaxyxwxbx$ I need to encode it in a way where every index stores the value of the number of unique characters ...