Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
1
vote
0answers
138 views

Approaches for analyzing the work, critical path length and parallelism

I'd like to know where to find references and approaches on how to analyze the work, critical path length and parallelism of algorithms. In particular, for solving the type of homework problems below:...
1
vote
1answer
44 views

Proof involving asymptotic complexity

The question in Proof of big-o propositions asked to prove: $O(f(n))=O(g(n))\iff\Omega(f(n))=\Omega(g(n))\iff\Theta(f(n))=\Theta(g(n))$ The accepted answer starts the proof with: Suppose that $...
1
vote
1answer
108 views

Recursion Time Complexity (Half n' Half)

This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity: Input: string $s = s_1,\ldots,s_n$, integer $k$ Go over all symbols $s_1,\ldots,s_n$, one by one ...
1
vote
1answer
157 views

Akra-Bazzi method integral diverges

I want to solve this recursion: $$T(n) = 5T(\frac{n}{5}) + \frac{n}{lg(n)}$$ My attempt and issue: None of the cases for master theorem apply here. I tried using Akra-Bazzi method (https://en....
1
vote
0answers
32 views

Cuckoo hashing with a stash: how tight are the bounds on the failure probability?

I was reading this very good summary of Cuckoo hashing. It includes a result (page 5) that: A stash of constant sizes reduces the probability of any failure to fall from $\Theta(1/n)$ to $\Theta(...
1
vote
1answer
34 views

Asymptotic notation and random variables

I have two random variables $X$ and $Y$ and I want to bound the value of one in terms of the other (for now, I don't care about the actual distribution of their values). Suppose that the two ...
0
votes
0answers
31 views

Deducing $3^f = o(3^g)$ from $f = o(g)$

I really need help solving the following question: Given: $$f(n) = o(g(n))$$ Prove: $$3^{f(n)} = o(3^{g(n)})$$ My attempt: I know that $\frac{f(n)}{g(n)} \xrightarrow{} 0 $. I need to prove that $f(...
1
vote
2answers
187 views

Average case analysis of linear search

Based on CLRS question 2.2: Consider linear search again. How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to ...
4
votes
1answer
62 views

The role of asymptotic notation in $e^x=1+𝑥+Θ(𝑥^2)$?

I'm reading CLRS and there is the following: When x→0, the approximation of $e^x$ by $1+x$ is quite good: $$e^x=1+𝑥+Θ(𝑥^2)$$ I suppose I understand what means this equation from math ...
2
votes
3answers
594 views

Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time?

This is a question posted for extra practice (i.e., not for credit): Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time? Explain. I'm not sure ...
2
votes
2answers
58 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 ...
2
votes
2answers
96 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 ...
1
vote
1answer
114 views

Master theorem: When a $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor

I was trying to solve the following question while reviewing master theorem. Which of the following asymptotically grows faster. (a) $ T(n) = 4T(n/2) + 10n $ (b) $ T(n) = 8T(n/3) + 24n^2 $ (c) $ T(...
0
votes
1answer
69 views

What impact does the modulo operator have in a for-loop?

Here's an example of what I mean: ...
6
votes
2answers
361 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 ...
0
votes
1answer
32 views

Trouble finding what this recurrence solves to [duplicate]

I have a recurrence relation of the form $T(n) = 2T(n/2)+O(1)$ I'm not sure how to deal with the big $O$-notation in the problem in order to start solving it ? Any help would be appreciated.
2
votes
2answers
674 views

Bubble Sort with “while” loop - why is average case n^2?

If Bubble Sort is written as: ...
1
vote
2answers
35 views

What does “bounded above” mean in Family of Bachmann–Landau notations?

Per wiki |f| is bounded above by g (up to constant factor) asymptotically with this concrete example, $$f(n) = \log n$$ $$g(n) = n^c = n^{0.000001}$$ Does "bounded above (up to constant factor)...
0
votes
0answers
40 views

how to compute $O(n^{0.000001})$ [duplicate]

this MIT course gives a formula about Big O $$n^{0.999999} \log n = O(n^{0.999999} \cdot n^{0.000001})$$ going through wiki, i cannot find a similar Big O properties or usages. how to compute $O(n^{...
1
vote
0answers
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?
2
votes
2answers
2k 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 ...
1
vote
1answer
38 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 ...
2
votes
2answers
273 views

Formulating the master theorem with Little-O- and Little-Omega notation

In a lecture of Algorithms of Data Structures (based on Cormen et al.), we defined the master theorem like this: Let $a \geq 1$ and $b \gt 1$ be constants, and let $T : \mathbb{N} \rightarrow \...
0
votes
0answers
26 views

Calculating the Complexity of a Two Part Algorithm

This is in relation to this post I made. I eventually solved this by the following approach: Take the un-ordered file with all the purchasing data and use the UNIX ...
2
votes
1answer
80 views

Asymptotic analysis with factorial and exponential

I'm solving a complexity question where I have: $$ n!/2^n $$ The goal is to find an upper bound for this. My idea is using the fact that: $$ n! = O(n^n)$$ $$ n!/2^n = O((n/2)^n) = O(n^n)$$ But is ...
2
votes
2answers
576 views

All superlinear runtime algorithms are asymptotically equivalent to convex function?

Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$? All the examples that I could think of satisfy the above ...
0
votes
0answers
33 views

Minimization with asymptotic assumption

Given the function $g(n,m)=\min\Big\{f(a,b)+f(n-a,c)+f(n,m-bc)\Big|\\a,b,c\ \ \text{with} \left\{\begin{matrix} a,\ b,\ n-a,\ c,\ m-bc \geq 0 \\ b\leq a! \\ c\leq (n-a)! \\ \end{matrix}\right. \Big\}...
2
votes
1answer
26 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 ...
0
votes
0answers
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 ...
1
vote
1answer
44 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 ...
7
votes
1answer
435 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!
2
votes
3answers
68 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 ...
2
votes
2answers
665 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 ...
0
votes
1answer
56 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, ...
0
votes
0answers
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 ...
0
votes
3answers
109 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})$$ ...
4
votes
1answer
52 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 ...
2
votes
1answer
70 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 ...
0
votes
1answer
65 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 ...
0
votes
0answers
43 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.
1
vote
0answers
91 views

What are the asymptotic bounds (upper bound on time complexity) of the following function?

I am trying to find the upper bound on time complexity of the recursive function defined by the following equation: $$Q(t) = \sum^{N}_{i=1} q_i \big(g_i^{\frac{1}{m-1}} + Q(t+1)^{\frac{m}{m-1}}\big)^{\...
0
votes
3answers
92 views

If my algorithm has complexity O(n!*n), can I just write O(n!), or do I have to keep it like O(n!*n)?

Just as I asked in the title: if my algorithm has complexity $O(n!\times n)$, can I just write $O(n!)$, or I have to keep it like $O(n!\times n)$?
3
votes
0answers
48 views

Worst Case Analysis of a Multivariate Recurrence of a Graph Algorithm

I have a graph algorithm that runs in: $$ T(n, m) = \begin{cases} c_1 & n \leq 2 \lor m = 1\\ T(n - i,\ m - j - k) + T(i, k) + c_2 m + c_3 n & m \leq (n-i)i\\ T(n - i,\ m) + T(i, m) + ...
1
vote
3answers
204 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$.
2
votes
1answer
126 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. ...
-1
votes
1answer
66 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
0
votes
0answers
32 views
2
votes
1answer
52 views

Proving Big Omega of a polynomial without limits

Here is the definition of $\Omega$: $f(n) = Ω(g(n))$ iff there exist positive constants $c$ and $n_0$ such that $f(n) \ge cg(n)$ for all $n\ge n_0$. Here is one theorem: If $f(n) = a_m n^m + \...
1
vote
0answers
67 views

Can I say θ(g(n)) is the intersection of Ω(g(n)) and O(g(n))?

Let's say Ω(g(n)) be a set representing the lower bound and O(g(n)) be another set representing the upper bound for some function f(n). Can I say that θ(g(n)) is the intersection of these two sets? ...
1
vote
1answer
48 views

Understanding the relations between O(g(n)), Θ(g(n)) and Ω(g(n)) [duplicate]

I was reading the Cormen, Leiserson, Rivest and Stein textbook, Introduction to Algorithms. The book explained the three asymptotic notations literally very well. However, there was this paragraph: ...

1 2 3
4
5
23