Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
0
votes
0answers
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. ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
-1
votes
2answers
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?
0
votes
0answers
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 ...
-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
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 ...
1
vote
0answers
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 ...
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
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 - ...
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
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 ...
1
vote
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β‹…...
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
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))$. ...
1
vote
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(...
1
vote
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: ...
1
vote
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-...
0
votes
1answer
41 views

Asymptotic complexity of Combination sum problem vs Coin change problem

I've been looking at the following combination sum problem: ...
2
votes
1answer
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))$ ?
0
votes
2answers
65 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
63 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
46 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
23 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
42 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
18 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 ...
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
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 ...
0
votes
0answers
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 ...
5
votes
2answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
3answers
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 ...
1
vote
1answer
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 ...
1
vote
2answers
47 views

Algorithms: Determining Asymptotic Notation from a given execution time

I'm studying for an Algorithms and Data Structure test. There is a type of question that is usually always asked by my professor but I don't know how to answer/solve it. Question 1: An Algorithm with ...
0
votes
1answer
68 views

Does $f(n)=\theta(g(\log{n}))$ imply $f(n)=\theta(\log{g(n)})$?

I am learning about algorithmic complexities and I have this claim which I need to prove or disprove: $f(n)$ and $g(n)$ are asymptotically positive functions, if $f(n)=\Theta(g(\log(n))$ then $f(n)=\...
0
votes
0answers
30 views

Asymptotics of reccurence relation

I need to tell whether $\quad\exists a \quad T(n) = \omega(n^2)$ $T(n) = T(\frac{n}{2}) + aT(\frac{n}{4}) + n^2\\\\ \forall n<10 \quad T(n) = 1$ And if there is such $a$ I need to find the ...
1
vote
1answer
19 views

For $T(n) = 16(T/4) + n^2\lg^3n$ prove: $T(n) = \Theta(n^2\lg^3n)$

Define: $ \lg x = \log_2x $. Let $ f(n), g(n) $ be some non-negative functions. Define $ f(n) = \Theta (g(n)) $ if $$ \exists c_1,c_2 \in R\colon 0 < c_1g(n) \leq f(n) \leq c_2g(n) $$ I want ...
0
votes
0answers
33 views

Big O notation of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$

What is the O-notation (or $\Theta$ notation ) of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$ ? Can I use Sterling approximation : $n! = \Theta(\sqrt{n}\left(\frac{n}{e}\right)^n)$ ...

1
2 3 4 5
…
23