Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
1,205
questions
0
votes
2answers
50 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 $
...
0
votes
3answers
70 views
If a function $f(n)=\Theta(g(n))$, does it follow that $f(n/k)=\Theta(g(n))$ for a constant $k$?
Suppose the following is true for some f(n) and g(n):
$f(n) = \Theta(g(n))$
Does that mean $f(n/k) = \Theta(g(n))$ for any value of $k>0$?
I know that for the above to be true, there must exist ...
2
votes
1answer
271 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 ...
1
vote
2answers
164 views
1
vote
2answers
101 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 ...
1
vote
0answers
26 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 ...
3
votes
1answer
114 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
1answer
148 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 ...
1
vote
2answers
110 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
vote
2answers
40 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
1answer
66 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
1answer
72 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
49 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
1answer
2k views
Runtime analysis of while-loop analysis
s = n
while (s > 4)
s = s / 2
else
s = s - 1
Let $T(n) = \Theta(S(n))$ where $S(n)$ is number of while-loop runs.
$S(n)=1 + S(n/2)$ if $n$ is even
$S(n)=...
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 ...
2
votes
1answer
9k views
T(n) = 2T (sqrt(n))+ log n Recurrence
I am aware that the question is asked before but i there is still a confusing part for me.
In book the solution is like that:
$T(n) = 2T(\sqrt{n}) + \log(n)$
$m = \log n$ yields
$T(2^m) = 2T(2^{m/2})...
0
votes
2answers
47 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
41 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
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
49 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
31 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
49 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 ...
2
votes
1answer
198 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
2answers
369 views
Induction proofs in Big-O notation
I'm not sure how go about this question:
Prove the following inequality. For a correct proof, we require a value of the constant $c>0$ and an $n \in \mathbb N$, such that $\forall n>N : f(x)<...
1
vote
1answer
48 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(\...
0
votes
0answers
21 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
49 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
28 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 deļ¬nitions of ...
1
vote
1answer
15 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
42 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
28 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
59 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
42 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
113 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
36 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
28 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
70 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
27 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
149 views
Asymptotic complexity of Combination sum problem vs Coin change problem
I've been looking at the following combination sum problem:
...
2
votes
1answer
45 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
69 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
72 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
58 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
66 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 ...
