Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
1,131
questions
2
votes
1answer
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 ...
-2
votes
0answers
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 ...
0
votes
1answer
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 $
...
1
vote
2answers
133 views
1
vote
0answers
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
1
vote
2answers
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$ ?"
...
1
vote
2answers
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$...
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
0
votes
0answers
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. ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
-1
votes
2answers
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?
0
votes
0answers
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 ...
-1
votes
1answer
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 ...
3
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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^...
1
vote
1answer
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$ ...
1
vote
1answer
42 views
Best case “skew height” of an arbitrary tree
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(\...
1
vote
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 ...
2
votes
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 -
...
2
votes
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:
<...
1
vote
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 ...
1
vote
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⋅...
0
votes
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 ...
0
votes
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 ...
1
vote
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))$.
...
1
vote
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(...
1
vote
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:
...
1
vote
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-...
0
votes
1answer
57 views
Asymptotic complexity of Combination sum problem vs Coin change problem
I've been looking at the following combination sum problem:
...
2
votes
1answer
40 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
66 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
65 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
47 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
24 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
24 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 ...
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
79 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.$$
1
vote
1answer
34 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
43 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
20 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 ...
