Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
0
votes
0answers
24 views

In Hashing-collison resolved by chaining: Intuition behind $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$

Hashing-collison resolved by chaining: $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$ I was going through the text Introduction to Algorithms by Cormen et. al. and in the ...
0
votes
0answers
50 views

Big $O$ approximation for $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$

I have the following complexity equation: $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$ with the base case $T(m)=1$. Is it possible to calculate a big $O$ approximation for such equation? What is the right ...
1
vote
1answer
29 views

Intuition of lower bound for finding the minimum of $n$ (distinct) elements is $n-1$ as dealt with in CLRS

I was going through the text Introduction to Algorithms by Cormen et. al. where there was a discussion regarding the fact that finding the minimum of a set of $n$ (distinct) elements with $n-1$ ...
4
votes
1answer
3k views

When is a bound asymptotically tight?

What does it mean that the bound $2n^2 = O(n^2)$ is asymptotically tight while $2n = O(n^2)$ is not? We use the o-notation to denote an upper bound that is not asymptotically tight. The definitions of ...
1
vote
1answer
16 views

Is it correct or incorrect to say that an input say $C$ causes an average run-time of an algorithm?

I was going through the text Introduction to Algorithm by Cormen et. al. where I came across an excerpt which I felt required a bit of clarification. Now as far as I have learned that that while the ...
2
votes
1answer
51 views

Clarifying $\sum_{h=0}^{\lfloor lg(n)\rfloor}\lceil\frac{n}{2^{h+1}}\rceil O(h)=O(n\sum_{h=0}^{\lfloor lg(n)\rfloor}\frac{h}{2^h})$ in BUILD-MAX-HEAP

I was going the text Introduction to Algorithms by Cormen et. al. Where I came across a step in the analysis of the time complexity of the $BUILD-MAX-HEAP$ procedure. The procedure is as follows: <...
0
votes
1answer
34 views

Clarifying statements involving asymptotic notations in soln of $T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$ using recursion tree and substitution

Below is a problem worked out in the Introduction to Algorithms by Cormen et. al. (I am not having problem with the proof but only I want to clarify the meaning conveyed by few statements in the text ...
1
vote
1answer
62 views

Show that $O(\text{max}\{f(n),g(n)\})=O(f(n)+g(n))$

Show that $O(\text{max}\{f(n),g(n)\})=O(f(n)+g(n))$ Can I keep the same constant $c$ in each of the cases? Consider two cases: $$1)f(n)>g(n);O(\text{max}\{f(n),g(n)\})⇒O(f(n))\Rightarrow d(n) ≤c⋅...
0
votes
1answer
59 views

Proving building a balanced BST out of sorted array is $\Theta(n)$

I'm having hard time proving building a balanced BST out of sorted array is $\Theta(n)$ I got the following formula: $$T(n)=2T(\frac{n}{2})+\Theta(1)$$ I tried to prove it by induction but got stuck ...
1
vote
3answers
167 views

Show that if $d(n)$ is $O(f(n))$, then $ad(n)$ is $O(f(n))$, for any constant $a > 0$?

Show that if $d(n)$ is $O(f(n))$, then $ad(n)$ is $O(f(n))$, for any constant $a > 0$? Does this need to be shown through induction or is it sufficient to say: Let $d(n) = n$ which is $O(f(n))$. ...
0
votes
1answer
45 views

What do we mean by polynomially upper bounded and lower bounded

I just came across this asymptotic bound : $(\log n)!= \Theta \left(n^{\log \log n}\right)$ Which had the following remark: Hence, polynomially lower bounded but not upper bounded. I ...
1
vote
1answer
36 views

Asymptotic of divide-and-conquer type recurrence with non-constant weight repartition between subproblems and lower order fudge terms

While trying to analyse the runtime of an algorithm, I arrive to a recurrence of the following type : $$\begin{cases} T(n) = \Theta(1), & \text{for small enough $n$;}\\ T(n) \leq T(a_n n + h(...
1
vote
1answer
90 views

Time complexity of code running at most summation(N) times in a loop

Let’s say I have a JavaScript loop iterating over input of size N. Let’s say all elements in N are unique, so the includes method traverses the entire output array on each loop iteration: ...
1
vote
1answer
62 views

Show that recurrence is $O(\phi^{\log n})

I have a function whose time complexity is given by the following recurrence: \begin{equation*} T(n) = \begin{cases} \mathcal{O}(1) & \text{for } n=0\\ T(k)+T(k-...
0
votes
1answer
28 views

Why substituting the search part in INSERTION SORT doesnt yield a running time of $\Theta(nlgn)$

$$ \Theta - Tight \ asymptotic \ bound $$ If we change lines $5-7$ in Insertion sort With BINARY-SEARCH(A,p,r,v) Why don't we get a running time of $\Theta(n\lg n)$ as we go through the array $\...
0
votes
1answer
245 views

Asymptotic complexity of Combination sum problem vs Coin change problem

I've been looking at the following combination sum problem: ...
2
votes
1answer
49 views

Does the product of two functions equal the product of their Big-O's?

let's say $f(n) = O(g(n))$ and $l(n) = O(m(n))$ is it always true that $f(n) \cdot l(n) = O(g(n)) \cdot O(m(n))$ ?
0
votes
2answers
74 views

How do I prove that $3x^3 +2x + 1 $ is $\omega(x \cdot \log x) $

I am trying to answer this question: $3x^3 +2x + 1$ is $ \omega(x \cdot \log x)$ My question is how to solve this question. Here is what I have tried so far: I applied the definition $3x^3 + 2x + 1 ...
2
votes
3answers
77 views

Little O notation relationship

Given the functions $𝑓(𝑛)=𝑛^{n}$ and $𝑔(𝑛)=10^{10n}$, I am trying to establish the following relationship: $𝑓(𝑛)\notin o(𝑔(𝑛))$. I know to show for the opposite, $𝑓(𝑛)\in o(𝑔(𝑛))$, I ...
1
vote
1answer
67 views

Solving a multivariate equation for asymptotic complexity

I have a function $f(m, n)$ with time complexity $T(m, n)$ characterized by the recurrence relation $$\begin{align} T(m,\ n) &= 2T\bigl(\frac{m}{2}, \frac{n}{2}\bigr) + c_0 \log n + c_1.\\ T(m,\ ...
1
vote
2answers
221 views

Show that the best case time complexity of Quicksort is $\Omega(n \log n)$

I am trying to show that the best case time complexity of Quicksort is $\Omega(n \log n)$. The following recurrence describes the best-case time complexity of Quicksort: $$T(n) = \min_{0 \le q \le n-...
0
votes
1answer
37 views

Time complexity analysis of 2 arbitrary algorithms - prove or disprove

We are given 2 algorithms A and B such that for each input size, algorithm A performs half the number of steps algorithm B performs on the same input size. We denote the worst time complexity of each ...
4
votes
3answers
2k views

Big O Notation of $n^{0.999999}\log(n)$

I'm taking the MIT Open Courseware for Introduction to Algorithms and I'm having trouble understanding the first homework problem/solution. We are supposed to compare the asymptotic complexity (big-O)...
1
vote
0answers
31 views

Heuristics for maximizing the performance for a given complexity

I often have to balance the computational requirement of each qualitatively different module of my algorithm. So, I'm using this heuristics for maximizing the performance for a given complexity, but I ...
2
votes
1answer
87 views

How to find a good asymptotic approximation of T(n) = T(n/2) + T(n/3) + 1?

I can't figure out how to find a good asymptotic approximation for the following recurrence relation: $$T(n) = T(n/2) + T(n/3) + 1.$$
0
votes
2answers
98 views

Big-O notation for the given function whose runtime complexity grows faster than the input

I struggle to determine the runtime complexity of a function I thought of while trying to solve this LeetCode quiz. The quiz itself goes like this: Write a program to find the n-th ugly number. Ugly ...
1
vote
1answer
79 views

Worst case running time of lexicographical sorting of a list of n strings each of length n using merge sort

This same question has been asked here so many times by several people. This is a problem which was asked in an entrance exam. And I am having difficulties in digesting the correct answer of this ...
-2
votes
1answer
51 views

What is the time complexity of the following triple nested loop? Kindly solve in term of n

I want to ask that what is the time complexity of this function (triple nested loop) .Kindly analysis completely so that I can understand. ...
1
vote
1answer
34 views

When computing asymptotic time complexity, can a variable dominate over other?

I want to express the asymptotic time complexity for the worst case scenario of sorting a list of $n$ strings, each string of length $k$ letters. Using merge-sort, sorting a list of $n$ elements ...
2
votes
3answers
2k 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 ...
0
votes
1answer
49 views

Why Is My Proof Of Asymptomatic Time Complexity Of A Dynamic Array Using The Accounting Method Getting A Wrong Answer?

I had trouble formatting the summation symbols, so if anyone knows how to do it correctly feel free to edit. I just read the asymptomatic analysis chapter from CLRS. While the aggregation and ...
5
votes
2answers
96 views

Why $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ doesn't refute the lower bound $O(n^{3-\delta})$?

I have a simple quesiton: It is conjectured that All Pairs Shortest Path (APSP) has no $O(n^{3-\delta)}$-time algorithm for any $\delta >0$ by SETH. also there is a result that says APSP can ...
1
vote
1answer
25 views

Solving recurrence

How to solve the recursion: $ T(n) = \begin{cases} T(n/2) + O(1), & \text{if $n$ is even} \\ T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + O(1), & \text{if $n$ is odd} \end{cases} $ I ...
2
votes
1answer
70 views

Solving recurrence relation for asymptotic analysis

How to solve the recursion: $ T(n) = \begin{cases} T(n/2) + O(1), & \text{if $n$ is even} \\ 2T(\lceil n/2 \rceil) + O(1), & \text{if $n$ is odd} \end{cases} $ I know that it can be ...
0
votes
0answers
14 views

Complexity simplification for complexity that consists of partial multiplication

For the algorithm that I have written the complexity is something like: a * e(A) + b * e(B) + b * e(C) + ... Where a represents the instance count of some node A and e(A) the edges outgoing of node ...
2
votes
3answers
193 views

Big-Oh of recursive function

Can someone please explain to me why this function runs in O($n^2$) rather than O($n^3$). I feel like since that for loop runs in O($n^2$) and f() is recursively called around n times, that it should ...
11
votes
2answers
18k views

Master theorem not applicable?

Given the following recursive equation $$ T(n) = 2T\left(\frac{n}{2}\right)+n\log n$$ we want to apply the Master theorem and note that $$ n^{\log_2(2)} = n.$$ Now we check the first two cases for $...
3
votes
1answer
2k views

Meaning of polynomially larger or smaller in the context of the master method

I'm studying the master method of solving recurrences and I have a somewhat decent math background but I'm having difficulty understanding the concept of $n^{\log_ba}$ being polynomially smaller or ...
1
vote
1answer
122 views

Using substitution method to prove asymptotic lower bound of $T(n) = T(n-1) + \Theta (n)$

I try to prove that the asymptotics of the recurrence $ T(n) = T(n-1) + \Theta (n) $ is $ T(n) = \Theta(n^2) $. By $\Theta$, I mean tight bound from above and below. I can write the equation like ...
1
vote
2answers
55 views

Algorithms: Determining Asymptotic Notation from a given execution time

I'm studying for an Algorithms and Data Structure test. There is a type of question that is usually always asked by my professor but I don't know how to answer/solve it. Question 1: An Algorithm with ...
0
votes
1answer
136 views

Does $f(n)=\theta(g(\log{n}))$ imply $f(n)=\theta(\log{g(n)})$?

I am learning about algorithmic complexities and I have this claim which I need to prove or disprove: $f(n)$ and $g(n)$ are asymptotically positive functions, if $f(n)=\Theta(g(\log(n))$ then $f(n)=\...
0
votes
0answers
30 views

Asymptotics of reccurence relation

I need to tell whether $\quad\exists a \quad T(n) = \omega(n^2)$ $T(n) = T(\frac{n}{2}) + aT(\frac{n}{4}) + n^2\\\\ \forall n<10 \quad T(n) = 1$ And if there is such $a$ I need to find the ...
4
votes
1answer
2k views

Algorithms with polynomial time complexity of higher order

I was learning about algorithms with polynomial time complexity. I found the following algorithms interesting. Linear Search - with time complexity $O(n)$ Matrix Addition - with time complexity $O(n^...
1
vote
1answer
47 views

For $T(n) = 16(T/4) + n^2\lg^3n$ prove: $T(n) = \Theta(n^2\lg^3n)$

Define: $ \lg x = \log_2x $. Let $ f(n), g(n) $ be some non-negative functions. Define $ f(n) = \Theta (g(n)) $ if $$ \exists c_1,c_2 \in R\colon 0 < c_1g(n) \leq f(n) \leq c_2g(n) $$ I want ...
0
votes
0answers
33 views

Big O notation of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$

What is the O-notation (or $\Theta$ notation ) of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$ ? Can I use Sterling approximation : $n! = \Theta(\sqrt{n}\left(\frac{n}{e}\right)^n)$ ...
2
votes
1answer
51 views

minimizing the maximum between a degree of a tree and its height

I'm interested in asymptotically minimizing the maximum between the height of a tree of degree $k$ with $n$ leaves, and $k$, i.e. minimizing $\max(k, \log_kn)$ asymptotically. If I set $k = \frac {\...
1
vote
1answer
227 views

Big O of rational function using the definition

I want to prove that $\dfrac{3x^3+2x^2+x+1}{4x^2+1}$ is $O(x)$. I am having problem in finding $c$ and $k$ and proving that it is big O, since the function involves a fraction. How would I go about ...
1
vote
1answer
175 views

Worst-case expected running time for Randomized Permutation Algorithm

I have an algorithm which, when given a positive integer N, generates a permutation of the first N integers (from 1 to N) using a method called randInt(x,y). The method randInt(x,y) will generate a ...
1
vote
0answers
44 views

Big O notations of some functions

What is the big-O notation of the following functions : $\displaystyle\sum_{i=1}^n \left(\begin{array}{c} n-1\\ i \end{array}\right)\\\\ \displaystyle\sum_{i=1}^{n} \sum_{j=1}^{n-i}(3j)\\\\ n^{\...
0
votes
1answer
36 views

Growth of exponential functions according to the big O notation

I'm preparing for an exam and trying to make some sense of the growth of the different exponential functions. I picked the trickiest functions for myself and tried to sort them according to the big O ...

1
3 4
5
6 7
26