Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
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

Time complexity of pairs in array double loop

I know, that the following is: O(n^2), ...
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 definitions 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 ...

1 2
3
4 5
25