# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,119 questions
Filter by
Sorted by
Tagged with
4 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. ...
36 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 ...
34 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 ...
39 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 ...
50 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?
23 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 ...
36 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 ...
12 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 129 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 15 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 53 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 42 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 22 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 49 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 60 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-...
41 views

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

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

26 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 ...
15 views

### Is the usage for asymptotic notation for these algorithms correct? [duplicate]

So after reading a lot of information around asymptotic analysis of algorithms and the use of Big O / Big Ω and Θ, I'm trying to grasp how to utilise this in the best way when representing algorithms ...
81 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 ...
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 ...
20 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 ...
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 ...
130 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 ...
13 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 ...