Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
4
votes
1answer
243 views
Asymptotics question
Is $\frac {n!} {2!\cdot 4!\cdot 8!\dots (n/2)!}=O(4^n)$?
I am really stuck and I tend to believe it's true, but I don't know how to prove it.
Any help would be appreciated!
-2
votes
0answers
23 views
Disprove efficiency $(\log n)^{(\log n)} \in$ O($n^{2}$) [on hold]
Disprove: $(\log n)^{(\log n)} \in$ O($n^{2}$)
1
vote
3answers
47 views
What is the asymptotic bound for $1n + 2(n-1) + 3(n-2) + … + (n-1)2 + n$?
My best guess is that the series
$$ \sum_{i=1}^n i(n-(i-1)) $$
becomes
$$ 2 \Bigg[ n + 2(n-1) + ... + \frac{n}{2} \bigg(n-\bigg(\frac{n}{2}-1\bigg)\Bigg)\Bigg] $$
So the highest term is $n^2$ and ...
1
vote
2answers
61 views
Traveling Salesman Problem: Big O Complexity of Algorithm
I'm trying to figure out how to do this problem in my intro algorithm class, but I'm a little confused.
The Traveling Salesman problem (TSP) is famous. Given a list of
cities and the distances ...
-1
votes
0answers
48 views
Exponential Complexity Homework Question
Im currently learning about algorithm analysis in my class and I came across this homework question. I really don't know where to start or what the question is asking for. Can someone guide me in the ...
0
votes
1answer
15 views
Is this computational complexity of the k-NN (custom distance) correct?
I read on a book that in general k-NN (no optimizations), given
$d$ dimensions
$n$ examples
every computation of distance is $O(d)$. Since every example has to be compared with all the other ones, ...
0
votes
0answers
21 views
Asymptotic Question [duplicate]
Hi how do I find the asymptotic bound for the recurrence T(n) = T(n/2) + T(n/4) + T(n/8) + n?
Can I use master theorem or Substitution method only?
If so, I need some help for substitution method. My ...
0
votes
3answers
57 views
How can i prove this asymptotic comparison? [duplicate]
This is an exercise that's part of my assignment, but it is optional and flagged as a "challenge". I would like to discuss its solution:
Prove that: $$ 27\log{n} + \sqrt{n} = \theta(\sqrt{n})$$
...
3
votes
1answer
37 views
Lower bound on $1^k+2^k+\dots+n^k$
I calculated the worst case scenario of a time complexity of an algorithm problem using recurrence tree. (The problem cannot be solved by master theorem.)
Now I want to find a lower bound on the ...
1
vote
1answer
31 views
Interpretation of an asymptotic notation
Assume that we measure the complexity of an algorithm (for some problem) by two parameters $n$ and $m$ (where $m \le n$). What is the formal interpretation of the following claim: there is no ...
0
votes
1answer
30 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
18 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
76 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
82 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
44 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
votes
0answers
116 views
Solving Recurrence
Given the recurrence
$\forall \{a_i\}\subseteq \mathbb N.\ \ T((\sum_i{a_i})!)\leq \sum_i {T(a_i!)+T((\sum_i {a_i})!-\prod_i (a_i!))}$
with $T(O(1))=O(1) $
How should I solve this?
I tried to ...
1
vote
3answers
62 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
64 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
61 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
0
votes
0answers
24 views
Is the time complexity of this function O(n^3)? And O(n) for its memoized solution?
Given this naive recursive function:
...
2
votes
1answer
25 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 + \...
1
vote
0answers
50 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
27 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:
...
1
vote
1answer
28 views
2
votes
2answers
38 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
32 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^...
0
votes
2answers
72 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
80 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 ...
1
vote
0answers
53 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 ...
-2
votes
2answers
71 views
How to solve equations using big Θ [duplicate]
How would I prove that the statement
$10n^3+3n=Θ(n^3)$
is true/false?
4
votes
2answers
63 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 ...
1
vote
1answer
21 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
83 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
1answer
42 views
Meaning of polynomially larger or smaller in the context of the master method
I'm studying the master method of solving recurrences and I have a somewhat decent math background but I'm having difficulty understanding the concept of $n^{\log_ba}$ being polynomially smaller or ...
2
votes
2answers
40 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
33 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
24 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
16 views
Solve Recurrence $T(n) = T(pn) + T((1-p)n) + \Theta(n)$ [duplicate]
For $0 < p < 1$, how can you solve the recurrence $$T(n) = T(pn) + T((1-p)n) + \Theta(n)$$ using the substitution method. My guess is $T(n) = O(n \log n)$, but plugging this guess in leads to a ...
0
votes
0answers
26 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
2answers
40 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
28 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
40 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 ...
0
votes
1answer
53 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 ...
7
votes
2answers
77 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\...
1
vote
0answers
31 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)$"
(...
2
votes
1answer
37 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))
...
1
vote
2answers
92 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)$?
4
votes
1answer
58 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 ...
