Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,006 questions
Filter by
Sorted by
Tagged with
39 views

How to use Master Theorem with strange format of $b$ parameter?

I have a funcion $T: \mathbb{N}\to\mathbb{N}$ defined as: $$T(n)=\begin{cases} 6 &\text{ if } n=0,\\ T(n-1) + 6n + 6 &\text{otherwise.} \end{cases}$$ How can I apply the Master Theorem to ...
88 views

Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)

We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently: $$T(n)=\begin{cases} 0 &\text{ if } n=0,\\ 3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.} \end{cases}$$ Prove that for ...
64 views

48 views

which rule can conduct this formula $\log n = O(n^{0.000001})$? [duplicate]

i am learning this post about Big O, which gives this formula $$\log n = O(n^{0.000001})$$ why is that?
1k views

Are “of the order of n” and “Big O” the same thing?

I am learning from the MIT course Introduction to Algorithms. The professor says: Now, remember $\Theta(n)$ is essentially something that says "of the order of $n$". What does "of the order ...
14 views

How can I assign the following functions f2,f3,f4 to the best possible (mostly restricted) asymptotic class? [duplicate]

Try a couple of ways but still having a problem to find the specific asymptotic class for each function. ¿Any reference to find the solution o aproach?
36 views

Asymptotics of a sinusoid

Consider the function $$f(n) = 2n^2 |\sin(\pi \cdot n/2)|.$$ Which of the following classes does $f(n)$ belong to? $$O(n^2), \Omega(n^2), \Theta(n^2), \omega(n^2), o(n^2).$$ I'm working in this ...
199 views

22 views

Proving that there exists a distance $d$-dominating set of size $O(n/\delta)$

Let $d > 1$, and consider a graph $G = (V,E)$ on $n$ vertices. A distance $d$-dominating set of $G$ is a set $D \subseteq V$ with the property that for any $v \in V$, either $v \in D$ or $v$ is at ...
36 views

How can I prove the linear time search algorithm takes O(n) time? [duplicate]

The recurrence relation for the algorithm is an eccentric form that has an additional term: $T(n) = T[\frac{n}{2}] + T[\frac{7n}{10} + 6] + n$. Exactly how can I prove that this recurrence relation ...
27 views

Comparing different asymptotic notations

Suppose we have 3 algorithms complexity times at the worst case: A = $O(nlogn)$ B = $O(n\sqrt{n})$ C = $\Theta(n)$ In my opinion, it is not possible to define the best solution, since we don't know ...
421 views

Asymptotics question

Is $\frac {n!} {2!\cdot 4!\cdot 8!\dots (n/2)!}=O(4^n)$? I am really stuck and I tend to believe it's true, but I don't know how to prove it. Any help would be appreciated!
64 views

What is the asymptotic bound for $1n + 2(n-1) + 3(n-2) + … + (n-1)2 + n$?

My best guess is that the series $$\sum_{i=1}^n i(n-(i-1))$$ becomes $$2 \Bigg[ n + 2(n-1) + ... + \frac{n}{2} \bigg(n-\bigg(\frac{n}{2}-1\bigg)\Bigg)\Bigg]$$ So the highest term is $n^2$ and ...
193 views

Traveling Salesman Problem: Big O Complexity of Algorithm

I'm trying to figure out how to do this problem in my intro algorithm class, but I'm a little confused. The Traveling Salesman problem (TSP) is famous. Given a list of cities and the distances ...
29 views

Is this computational complexity of the k-NN (custom distance) correct?

I read on a book that in general k-NN (no optimizations), given $d$ dimensions $n$ examples every computation of distance is $O(d)$. Since every example has to be compared with all the other ones, ...
22 views

Asymptotic Question [duplicate]

Hi how do I find the asymptotic bound for the recurrence T(n) = T(n/2) + T(n/4) + T(n/8) + n? Can I use master theorem or Substitution method only? If so, I need some help for substitution method. My ...
75 views

How can i prove this asymptotic comparison? [duplicate]

This is an exercise that's part of my assignment, but it is optional and flagged as a "challenge". I would like to discuss its solution: Prove that: $$27\log{n} + \sqrt{n} = \theta(\sqrt{n})$$ ...
50 views

Lower bound on $1^k+2^k+\dots+n^k$

I calculated the worst case scenario of a time complexity of an algorithm problem using recurrence tree. (The problem cannot be solved by master theorem.) Now I want to find a lower bound on the ...
53 views

Interpretation of an asymptotic notation

Assume that we measure the complexity of an algorithm (for some problem) by two parameters $n$ and $m$ (where $m \le n$). What is the formal interpretation of the following claim: there is no ...
51 views

How to find examples of best cases for sorting algorithms?

I am asked to give a table of 8 elements that are to be sorted by the following algorithms and to produce their best cases. 1) Selection sort 2) Bubble sort 3) Insertion sort 4) Fusion sort If I give ...
34 views

Substitution method for $T(n) = 2T(7n/10) + O (1)$ [duplicate]

I want to solve $T(n) = 2T(7n/10) + O (1)$ using the substitution method. I think the solution should be $T(n) = O(n\log n)$, but I am having trouble constructing a proof by substitution.
83 views

91 views

Solving $T(n)=4T(n/2)-1$ without using the master theorem [duplicate]

How can I solve the following recurrence without using the master theorem? $T(n)= 4T(n/2)-1$ for $n>4$ and $T(n)=5$ for $n\le 4$, $n$ is a power of $2$.
92 views

How do I describe formally complexity of 2-sum problem algorithm?

I have algorithm that finds if there are two elements in sorted array that have sum zero. ...
63 views

Prove $8^n = Θ(4^n)$

how would I prove $8^n = Θ(4^n)$ is either true or false. I so far have attempted to prove big O but cant find the value of C1
31 views

Is the time complexity of this function O(n^3)? And O(n) for its memoized solution?

Given this naive recursive function: ...
30 views

303 views

proving big theta [duplicate]

How would I tackle this equation? $$10n^3 +3n = \Theta(n^3)$$ I know I have to solve Big $O$ and Big $\Omega$ but have no idea how to do this. I got as far as $$10n^3+3n \leq c_1n^3$$ 0 \leq ...
87 views

Can all $O(n)$ problems be solved without nested loops?

There are examples of algorithm implementations that contain nested loops but are of complexity O(n), and some of them have corresponding implementations that contain no nested loops. So here comes a ...
63 views

How to find big-O for an in-place perfect shuffle algorithm

I've found a simple algorithm to interleave two halves of an array in place. It involves swapping the first 1/2 of the items into the correct place, then unscrambling the permutation of the 1/4 of ...
110 views

How to solve equations using big Θ [duplicate]

How would I prove that the statement $10n^3+3n=Θ(n^3)$ is true/false?
On page 53 or CLRS it has said : We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function $g(n,m)$, we denote ...
Given a binary tree with labels on the leaves, like $(bc)(ad)$ or $((af)e)(c(db))$, which we can interpret as a product of terms with respect to a commutative associative operation, how many ...