# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,100 questions
Filter by
Sorted by
Tagged with
563 views

### Solving a recurrence with the Master Theorem

Problem taken from here (page 3): http://cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-Handout.pdf $T(n) = 3T(\frac{n}{2}) + \frac{3}{4}n + 1$ $f(n) = \frac{3}{4}n + 1$ It says we cannot use ...
29 views

98 views

### Intersection of functions given asymptotic relationship

If $f(n) = O(g(n))$ and $g(n) \neq O(f(n))$ than can we say that $f(n)$ and $g(n)$ will never intersect?
213 views

### Complexity for minimum subset sum of size n-k

Disclaimer: Not a HW. Given $n$ sorted positive floating point numbers, and one has to find the minimum subset sum of size $n-k$. What would be the most efficient way? I can figure out using Brute ...
510 views

### Want to understand Big O by graph [duplicate]

f(n) = 3n+3 ; f(n) = O(n) By definition : $3n+3 \le c_1.n$ By dividing both side by n $3+(3/n) \le c_1$ means we ...
169 views

### Building a Hyper Computer

I had an idea for a theoretical super computer. Supposing, one was able to optimise(or significantly increase efficiency) all algorithms used in most computing tasks(An open source project on ...
838 views

### How long would it take a computer with twice the processing power to solve a polynomial time problem?

Say I have some problem of $O\left(n^k\right)$ complexity. If I were to solve the problem on a computer $x$, it would take time $t$. Now I have a new computer $x'$, which has double the computing ...
142 views

### Using Big $O,\Omega,\Theta$, how would you represent these equations?

How would you write the following equations in $O,\Omega,\Theta$ notation? \begin{align*} t(n) &= 4n^4 + 3n^5 + 3n^6 \\ g(n) &= 2n^6 + 5\log n \\ f(n) &= 50n^5 \end{align*}
Let $A = \{ g(n) \mid \exists c,n_0 \, \forall n \ge n_0\colon g(n) \le cf(n) \}$, and $B = \{ g(n) \mid \exists c,n_0 \, \forall n \geq n_0 \colon g(n) < cf(n) \}$. Prove $A = B$. My ...