# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,131 questions
Filter by
Sorted by
Tagged with
30 views

### Asymptotic analysis of $T(n) = T(n/5) + T(4n/5) + \Theta(n)$

If I have a recurrence relationship like this: $$T(n) = T(n/5) + T(4n/5) + \Theta(n),$$ how would I analyze its rate of growth? I believe I can't use the master theorem. I tried to draw a tree but ...
26 views

### Asymptotic Complexity Proofs

Let $f, g : \mathbb{N}\to\mathbb{R}$ be two real-valued functions greater than $1$. Consider the following two statements: (A) $f(n) = \Theta(g(n))$ (B) $\log f(n) \sim \log g(n)$ (a) Prove: (B) does ...
31 views

### Choosing Constant for Last Step in Substitution METHOD $T(n)= 5T(n/4) + n^2$

I figured out a solution to a recurrence relation, but I'm not sure what the constant should be for the last step to hold. $T(n)= 5T(n/4) + n^2$ Guess: $T(n) = O(n^2)$ Prove: $T(n) \leq cn^2$ ...
133 views

### Time complexity of pairs in array double loop

I know, that the following is: O(n^2), ...
20 views

### Constant in Substitution method for recurrence

The solution for solving the following recurrence with the substitution method involves adding the a constant inside the recurrence, which is confusing to me. This is question 4.3-2 in the CLRS ...
28 views

### Is My Recurrence Solution Correct? (Substitution method) [closed]

I need to solve this recurrence via the substitution method. I'm not good at this and don't know if this proof is correct or not. My primary question is about choosing an $n_0$ and $c$ in a proof like ...
77 views

### Why Study Complexity Theory?

I’m an amateur in the study of algorithms. For a while I’ve had a burning question, why do we study complexity theory in computer science? The reason I ask is because algorithms with better ...
95 views

### Can $n = O(n^2)$?

I'm reading Data Structures and Algorithms by Goodrich. The explanation that he gives for Big Oh notation is given below: Let $f(n)$ and $g(n)$ be functions mapping positive integers to positive real ...
49 views

### How to prove ln(n) = Θ(log2 n)?

This is a homework problem and I'm not sure how to do it correctly. It says "Prove ln(n) = Θ(log2 n) with n = odd number". Bu using Natural logarithm rules, we can somehow know this is ...
36 views

### Big O notation for Average case in Linear search

Average case complexity for linear search is (n+1)/2 i.e, half the size of input n. The average case efficiency of an algorithm can be obtained by finding the average number of comparisons as given ...
39 views

### Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$?

I have encountered the following question in my homework assignment in Data Structures course: "Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$ ?" ...
69 views

### Solving unusual recurrence with two variables

I have the following recurrence relation: $$T(n,k) = T(n-1,k)+T(n-1,k+1)$$ With the following base cases (for some given constant $C$): For all $x \leq C$ and for any $k$: $T(x,k)=1$ For all $y \geq C$...
55 views

### What is Simple Uniform Hashing, and why searching a hashtable has complexity Θ(n) in the worst case

Can anyone explain nicely what Simple Uniform Hashing is, and why searching a hashtable has complexity Θ(n) in the worst case if we don’t have uniform hashing (where n is the number of elements in the ...
36 views

### How to know if time complexity is O(n+m) or O(n*m)

I'm having difficulty understanding when can we know if the time complexity of an algorithm is n+m or n*m Is the time complexity of the following algo O(n+m) or O(n*m) Can you please point me to a ...
11 views

### What does increasing the input size by a factor of 100 do to a linearthimic algorithm with the complexity of 2nlog(n)

So far what I've tried to do is break this into parts and work from there So for the $2n$, increasing by a factor of 100 means the runtime goes up by 100 times But I get stuck with the log(n) part. ...
44 views

### Complexity Values for Specific Code/Functions

(1) Assume a function $f:\mathbb{Z^+}\rightarrow\mathbb{R}$ that's defined in a way that utilizes, say, eight basic computations, including addition, subtraction, division, multiplication, (positive ...
38 views

### How to solve recursion with two separate converges rates

What is the correct way to solve the following recursion: $T(n)=T(\lceil\frac{n}{2}\rceil) + T(n-2)$ Or basically any recursion that has two parts which converge in a different rate. I'm trying to get ...
64 views

### Does $20n$ belong to $O(n^{1-\epsilon})$ for some $\epsilon > 0$?

I am quite new to master theorem and I would like to ask the following question for $$𝑇(𝑛)=4𝑇(𝑛/4)+20𝑛.$$ If there is a constant value like $20n$ does it affect the equation? Would the equation ...
54 views

### Which is more efficient? lg(n+10^n) higher than 2^lgn [duplicate]

Based on the order by asymptotic growth rate which is more efficient?
25 views

### Calculating the running time of Quicksort's PARTITION procedure

I am confused about calculating the PARTITION procedure's running time. PARTITION procedure is used in the Quicksort Algorithm to partition the array $A[p...r]$ I analyzed the PARTITION procedure ...
29 views

### If $j − 1 < \log k < j$. Why is $j = O(\log k)$?

If $j \in Z^+$ and $k \in R^+$ and $j − 1 < \log k < j$. Why is $j = O(\log k)$? (All log's are in base 2) I know I have to find constants where $j <= c \cdot \log k$ but I need some help ...
40 views

### What is considered an asymptotic improvement for graph algorithms?

Lets say we are trying to solve some algorithmic problem $A$ that is dependent on input of size $n$. We say algorithm $B$ that runs in time $T(n)$, is asymptotically better than algorithm $C$ which ...
13 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 ...
46 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 ...
46 views

### What is the upper and lower bound for $T(n) = T(\sqrt{n}) +3$, assuming that $T(n)$ is a constant for $n\leq 10$

By unrolling the recursion, \begin{equation*} \begin{split} T(n) &= T(\sqrt{n}) + 3 = T(n^{\frac{1}{2}}) + 3 \\ &= (T(n^{\frac{1}{4}})+3) +3 = T(n^{\frac{1}{4}}) +6 \\ &= (T(n^...
24 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$ ...
42 views

Given an arbitrary binary tree on $n$ nodes, choose an assignment $A$ from each parent to one of its children (the "favored child" as it were). We define the skew height of the tree as $H_A(\... 1answer 12 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 ... 1answer 141 views ### Average number of exchanges during first partition stage in Quicksort I am trying to understand average no of exchanges in Quicksort. Here is the code to partition the array - ... 1answer 40 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: <... 1answer 16 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 ... 1answer 54 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⋅... 1answer 37 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 ... 1answer 31 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 ... 3answers 55 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)). ... 1answer 25 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(... 1answer 53 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: ... 1answer 61 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-...
57 views

### Asymptotic complexity of Combination sum problem vs Coin change problem

I've been looking at the following combination sum problem: ...
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))$ ?