Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
0
votes
1answer
65 views

How to find examples of best cases for sorting algorithms?

I am asked to give a table of 8 elements that are to be sorted by the following algorithms and to produce their best cases. 1) Selection sort 2) Bubble sort 3) Insertion sort 4) Fusion sort If I give ...
0
votes
0answers
43 views

Substitution method for $T(n) = 2T(7n/10) + O (1)$ [duplicate]

I want to solve $T(n) = 2T(7n/10) + O (1)$ using the substitution method. I think the solution should be $T(n) = O(n\log n)$, but I am having trouble constructing a proof by substitution.
1
vote
0answers
88 views

What are the asymptotic bounds (upper bound on time complexity) of the following function?

I am trying to find the upper bound on time complexity of the recursive function defined by the following equation: $$Q(t) = \sum^{N}_{i=1} q_i \big(g_i^{\frac{1}{m-1}} + Q(t+1)^{\frac{m}{m-1}}\big)^{\...
0
votes
3answers
90 views

If my algorithm has complexity O(n!*n), can I just write O(n!), or do I have to keep it like O(n!*n)?

Just as I asked in the title: if my algorithm has complexity $O(n!\times n)$, can I just write $O(n!)$, or I have to keep it like $O(n!\times n)$?
3
votes
0answers
48 views

Worst Case Analysis of a Multivariate Recurrence of a Graph Algorithm

I have a graph algorithm that runs in: $$ T(n, m) = \begin{cases} c_1 & n \leq 2 \lor m = 1\\ T(n - i,\ m - j - k) + T(i, k) + c_2 m + c_3 n & m \leq (n-i)i\\ T(n - i,\ m) + T(i, m) + ...
1
vote
3answers
197 views

Solving $T(n)=4T(n/2)-1$ without using the master theorem [duplicate]

How can I solve the following recurrence without using the master theorem? $T(n)= 4T(n/2)-1$ for $n>4$ and $T(n)=5$ for $n\le 4$, $n$ is a power of $2$.
2
votes
1answer
124 views

How do I describe formally complexity of 2-sum problem algorithm?

I have algorithm that finds if there are two elements in sorted array that have sum zero. ...
-1
votes
1answer
66 views

Prove $ 8^n = Θ(4^n)$

how would I prove $ 8^n = Θ(4^n)$ is either true or false. I so far have attempted to prove big O but cant find the value of C1
2
votes
1answer
47 views

Proving Big Omega of a polynomial without limits

Here is the definition of $\Omega$: $f(n) = Ω(g(n))$ iff there exist positive constants $c$ and $n_0$ such that $f(n) \ge cg(n)$ for all $n\ge n_0$. Here is one theorem: If $f(n) = a_m n^m + \...
90
votes
11answers
19k views

Solving or approximating recurrence relations for sequences of numbers

In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested ...
2
votes
0answers
93 views

How to find big-O for an in-place perfect shuffle algorithm

I've found a simple algorithm to interleave two halves of an array in place. It involves swapping the first 1/2 of the items into the correct place, then unscrambling the permutation of the 1/4 of ...
1
vote
0answers
66 views

Can I say θ(g(n)) is the intersection of Ω(g(n)) and O(g(n))?

Let's say Ω(g(n)) be a set representing the lower bound and O(g(n)) be another set representing the upper bound for some function f(n). Can I say that θ(g(n)) is the intersection of these two sets? ...
1
vote
1answer
38 views

Time complexity of recurrence function with if statement

Given the following code. ...
1
vote
1answer
47 views

Understanding the relations between O(g(n)), Θ(g(n)) and Ω(g(n)) [duplicate]

I was reading the Cormen, Leiserson, Rivest and Stein textbook, Introduction to Algorithms. The book explained the three asymptotic notations literally very well. However, there was this paragraph: ...
2
votes
2answers
46 views

What is wrong with this solution for $\mathcal{O}({\log({n \choose \frac{n}{2}})})$?

In this recitation on MIT OCW, the instructor uses Stirling's approximation to calculate that $\mathcal{O}({\log({n \choose \frac{n}{2}})}) = \mathcal{O}(n)$. However, I went through the following ...
1
vote
1answer
43 views

Asymptotic complexity of function with two Input variables

Suppose I have a function with two input below. $f(m,n) = \log {n^m} + 100n \log \log {m^5} + 150m + 4n^2 + 1000$. Is it safe to say that $f(m,n)$ is $\mathcal{O}(m \log n)$, or is it $\mathcal{O}(n^...
-2
votes
2answers
163 views

How to solve equations using big Θ [duplicate]

How would I prove that the statement $10n^3+3n=Θ(n^3)$ is true/false?
0
votes
2answers
859 views

proving big theta [duplicate]

How would I tackle this equation? $$10n^3 +3n = \Theta(n^3)$$ I know I have to solve Big $O$ and Big $\Omega$ but have no idea how to do this. I got as far as $$10n^3+3n \leq c_1n^3$$ $$0 \leq ...
2
votes
1answer
102 views

Can all $O(n)$ problems be solved without nested loops?

There are examples of algorithm implementations that contain nested loops but are of complexity O(n), and some of them have corresponding implementations that contain no nested loops. So here comes a ...
0
votes
3answers
166 views

What is the asymptotic complexity of the following code snippet?

for (i = 2; i < n; i = i * i) { for (j = 1; j < i / 2; j = j + 1) { sum = sum + 1; } } I know that the outer loop can run for a maximum of $n^2$ ...
4
votes
2answers
72 views

Order Mistake Definition in CLRS

On page 53 or CLRS it has said : We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function $g(n,m)$, we denote ...
2
votes
1answer
43 views

Minimum number of tree operations to normalize a labeled tree

Given a binary tree with labels on the leaves, like $(bc)(ad)$ or $((af)e)(c(db))$, which we can interpret as a product of terms with respect to a commutative associative operation, how many ...
1
vote
1answer
97 views

To check if a chain with $n$ links can be “folded” into a size at most $L$

Given a chain of $n$ links, each of length $a_1, a_2,..a_n$, where each $a_i$ is a positive integer. $L$ defines the length of the "folded" chain. More formally, we want to decide whether there exists ...
2
votes
2answers
24 views

Maximum Changes that don't Break the Build

Let's say I have a set of changes, e.g. replacing foo with bar in a codebase, how do I programmatically discover the largest set ...
2
votes
2answers
44 views

Why is $\binom{n}{f}^g=O(n^{fg})$ true?

Why is it true? I understand why $n^g$ but how does the $f$ get there in the power?? I believe from the context that it's not just that $\binom{n}{f}^g$ is strictly smaller than $n^{f g}$, but rather ...
0
votes
1answer
42 views

Have I proved $\sum_{i=1}^{\lg n} 2^{i-1} = \Theta(n\lg n)$?

I have an exercise problem and don't know why its answer is like this. $$ \sum_{i=1}^{\lg n} 2^{i-1} \in \Theta(2^{\lg n}) = \Theta(n). $$ Regarding this equation, I think it would be, $$ \sum_{i=1}...
-1
votes
1answer
29 views

Is $\sum_{i=1}^n i \in \Theta(n^2)$?

Please help me understand on how to prove or disprove the following. I have been practicing and doing others which are ok, but with this sum, it is rather confusing. $$\sum_{i=1}^n i \in \Theta(n^2)...
0
votes
0answers
28 views

Can the average case of an algorithm be $O(n \log n)$ if the best case running time of an algorithm is $\Theta(n \log n)$? [duplicate]

Let us suppose the best case running time of an algorithm is $\Theta(n \log n)$. Can the average case run time of the algorithm be $O(n \log n)$? Since $O(n\log n)$ would imply the value going even ...
0
votes
1answer
119 views

What time complexity (big o) is this specific web crawler implementation?

Note: this question was marked as a duplicate in favor of this question/answer which attempts to provide a generic formula for translating code to mathematics. Unfortunately I didn't find that ...
0
votes
2answers
84 views

Showing that $\lg(n!)$ is or is not $o(\lg(n^n))$ and $\omega(\lg(n^n))$

My instructor assigned a problem that asks us to determine which asymptotic bounds apply to a certain $f(n)$ for a certain $g(n)$, in my case $f(n) = \lg(n!)$ and $g(n) = \lg(n^n)$. For clarity, the ...
1
vote
1answer
57 views

Solving the recurrence $T(n) = n^{3/4}𝑇(𝑛^{1/4})+ n $

I need to solve the following recurrence relation: $T(n) = n^{3/4}𝑇(𝑛^{1/4})+ n $. Obviously, the master theorem doesn't apply here so I was using the substitution method. I used $x=\log n$ and $F(x)...
1
vote
1answer
15 views

Algorithm notation between two functions [duplicate]

I have two functions, $$ f = n^{1.6} $$ $$ g = n^{1.5} $$ I thought this is $ f=\theta(g) $, since $ f $ is asymptotically tight bound of $ g $, if $ n $ goes to infinity. However, the answer is $ f ...
2
votes
1answer
114 views

All pair shortest path in a tripartite graph

I have a tri-partite graph with three sets of vertices source, bridge and destination nodes. I want to find the shortest path between every vertex in the source set to every vertex in the destination ...
1
vote
0answers
34 views

Prove that the upper bound for T(n)=T(an)+T(bn)+O(n) is O(n) [duplicate]

While learning Median of Medians algorithm i came across the following lemma ; "For any recurrence of the form $T(n)<=T(an)+T(bn)+O(n) $, if $(a+b)<1$ the reccurence will solve to $O(n)$" (...
7
votes
2answers
698 views

The recursion $T(n) = T(n/2)+T(n/3)+n$

I'm looking at the reccurrence $$T(n) = T(n/2) + T(n/3) + n,$$ which describes the running time of some unspecified algorithm (base cases are not supplied). Using induction, I found that $T(n) = O(n\...
2
votes
1answer
40 views

Solving T(n) = T(n-1)*T(n-2)

So, this is how I solved $\displaystyle T(n-1) \approx{} T(n-2) $ $\displaystyle T(n) = T(n-1)^2 $ Add log in both sides $\displaystyle log(T(n)) = 2log(T(n-1)) ...
2
votes
1answer
561 views

What is the relationship/difference between best/worse/expected case and big O/omega/theta? [duplicate]

In the big O section of Cracking the Coding Interview 6th edition, I read the following. ...
1
vote
2answers
679 views

Does converting adjacency matrix representation of graph of size $n \times n$ to adjacency list always require $O(n^2)$ time?

Assume that I have the adjacency matrix representation of a graph in $0,1$ values. Does converting it to a corresponding adjacency list representation always have a time complexity of $O(n^2)$?
5
votes
1answer
174 views

Why integer division is of equal complexity as multiplication

I am trying to understand the fact that integer division is no more difficult than integer multiplication. I found some references - here and this lecture note. Wikipedia says if there is a way to ...
-1
votes
1answer
104 views

Analyzing asymptotic notation $\sqrt n = O(\log^2 n)$

I am trying to determine whether $f(n) = \sqrt n$ is in $O(g(n))$, $\Omega(g(n))$, or $\Theta(g(n))$ where $g(n) = \log^2 n$. The answer says that only $f(n) = \Omega(g(n))$ is correct, but why isn't ...
1
vote
1answer
41 views

Asymptotic relation between n! and (n+1)!

I am having difficulty writing this formally. I know that by L'Hospital's rule we can reduce it to $\lim_{n \to \infty} \frac{n+1}{n}$ which is a constant and hence $n = \theta (n+1)!$. But I am not ...
1
vote
1answer
79 views

Master Method: $T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$

I'm having a hard time trying to understand how to solve this recurrence relation using the Master Method: $$T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$$ First, we have: $a = 10,\ b = 2$ ...
4
votes
2answers
7k views

If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))?

I guess this is true, because log is a strictly increasing function, but how do I prove it formally? I tried something like: Let $f(n)$ and $g(n)$ be monotonically increasing functions, $c \in \...
0
votes
1answer
27 views

Algorithm comparison

I am learning Big O and Big theta notation and confused the certain case. I have two functions, function 1(f1) $$ n * n^{1/2} $$ function 2(f2) $$ 1.001^n $$ in smaller cases (10,000) f1 is much ...
0
votes
0answers
29 views

The applicability of the Master Theorem and calculation of asymptotic limits

Given the following recursive equation $T(n)=3T(\dfrac{n}{8})+ Θ(n^{1/3})$ I want to know how to explain the applicability of the Master theorem in a rigorous way and what means asymtotic limits of ...
2
votes
2answers
73 views

Meaning of $ e^x = 1 + x + Θ(x^2)$?

In the CLRS chapter 3: When $x → 0$, the approximation of $e^x$ by $1+x$ is quite good: $$e^x = 1 + x + Θ(x^2).$$ How is it to be interpreted, what is the role of asymptotic notation here?
7
votes
4answers
231 views

What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?

We have a function which takes an array as input. It breaks an array into $\log_2(n)$ parts with equal sizes where $n$ is the size of the subarray. It keeps breaking each of the subarrays until there ...
1
vote
2answers
142 views

Running Time of Sorting Algorithm

Determine the asymptotic running time of the sorting algorithm maxSort. Algorithm maxSort(A) Input: An integer array A Output: Array A sorted in non-decreasing order ...
1
vote
1answer
48 views

Are the following Big Oh Notations equivalent?

In the context of Upper bounds computaion and Big Oh Notation, I was wondering if the following could be proved... if they are equivalent. $\mathcal{O}((log(n))^{-1}) = (\mathcal{O}(log(n)))^{-1}$ $\...

1
3 4
5
6 7
22