Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
1
vote
1answer
5 views
How to use Master Theorem with strange format of $b$ parameter?
I have a funcion $T: \mathbb{N}\to\mathbb{N}$ defined as:
$$T(n)=\begin{cases}
6 &\text{ if } n=0,\\
T(n-1) + 6n + 6 &\text{otherwise.}
\end{cases}$$
How can I apply the Master Theorem to ...
2
votes
2answers
45 views
Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (reccurence relation)
We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently:
$$T(n)=\begin{cases}
0 &\text{ if } n=0,\\
3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.}
\end{cases}$$
Prove that for ...
1
vote
1answer
43 views
Master theorem: When a $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor
I was trying to solve the following question while reviewing master theorem.
Which of the following asymptotically grows faster.
(a) $ T(n) = 4T(n/2) + 10n $
(b) $ T(n) = 8T(n/3) + 24n^2 $
(c) $ T(...
0
votes
1answer
33 views
3
votes
1answer
99 views
Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?
I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in ...
0
votes
1answer
31 views
Trouble finding what this recurrence solves to [duplicate]
I have a recurrence relation of the form $T(n) = 2T(n/2)+O(1)$
I'm not sure how to deal with the big $O$-notation in the problem in order to start solving it ? Any help would be appreciated.
3
votes
2answers
96 views
1
vote
2answers
33 views
What does “bounded above” mean in Family of Bachmann–Landau notations?
Per wiki
|f| is bounded above by g (up to constant factor) asymptotically
with this concrete example,
$$f(n) = \log n$$
$$g(n) = n^c = n^{0.000001}$$
Does "bounded above (up to constant factor)...
0
votes
0answers
29 views
how to compute $O(n^{0.000001})$ [duplicate]
this MIT course gives a formula about Big O
$$n^{0.999999} \log n = O(n^{0.999999} \cdot n^{0.000001})$$
going through wiki, i cannot find a similar Big O properties or usages.
how to compute $O(n^{...
1
vote
0answers
48 views
which rule can conduct this formula $\log n = O(n^{0.000001})$? [duplicate]
i am learning this post about Big O, which gives this formula
$$\log n = O(n^{0.000001})$$
why is that?
2
votes
2answers
1k views
Are “of the order of n” and “Big O” the same thing?
I am learning from the MIT course Introduction to Algorithms.
The professor says:
Now, remember $\Theta(n)$ is essentially something
that says "of the order of $n$".
What does "of the order ...
0
votes
0answers
14 views
How can I assign the following functions f2,f3,f4 to the best possible (mostly restricted) asymptotic class? [duplicate]
Try a couple of ways but still having a problem to find the specific asymptotic class for each function.
¿Any reference to find the solution o aproach?
1
vote
1answer
34 views
Asymptotics of a sinusoid
Consider the function
$$
f(n) = 2n^2 |\sin(\pi \cdot n/2)|.
$$
Which of the following classes does $f(n)$ belong to?
$$ O(n^2), \Omega(n^2), \Theta(n^2), \omega(n^2), o(n^2). $$
I'm working in this ...
2
votes
2answers
167 views
Formulating the master theorem with Little-O- and Little-Omega notation
In a lecture of Algorithms of Data Structures (based on Cormen et al.), we defined the master theorem like this:
Let $a \geq 1$ and $b \gt 1$ be constants, and let $T : \mathbb{N} \rightarrow \...
0
votes
0answers
25 views
Calculating the Complexity of a Two Part Algorithm
This is in relation to this post I made. I eventually solved this by the following approach:
Take the un-ordered file with all the purchasing data and use the UNIX ...
2
votes
1answer
26 views
Asymptotic analysis with factorial and exponential
I'm solving a complexity question where I have:
$$ n!/2^n $$
The goal is to find an upper bound for this.
My idea is using the fact that:
$$ n! = O(n^n)$$
$$ n!/2^n = O((n/2)^n) = O(n^n)$$
But is ...
2
votes
2answers
379 views
All superlinear runtime algorithms are asymptotically equivalent to convex function?
Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$?
All the examples that I could think of satisfy the above ...
0
votes
0answers
32 views
Minimization with asymptotic assumption
Given the function
$g(n,m)=\min\Big\{f(a,b)+f(n-a,c)+f(n,m-bc)\Big|\\a,b,c\ \ \text{with}
\left\{\begin{matrix}
a,\ b,\ n-a,\ c,\ m-bc \geq 0 \\
b\leq a! \\
c\leq (n-a)! \\
\end{matrix}\right.
\Big\}...
2
votes
1answer
22 views
Proving that there exists a distance $d$-dominating set of size $O(n/\delta)$
Let $d > 1$, and consider a graph $G = (V,E)$ on $n$ vertices. A distance $d$-dominating set of $G$ is a set $D \subseteq V$ with the property that for any $v \in V$, either $v \in D$ or $v$ is at ...
0
votes
0answers
36 views
How can I prove the linear time search algorithm takes O(n) time? [duplicate]
The recurrence relation for the algorithm is an eccentric form that has an additional term: $T(n) = T[\frac{n}{2}] + T[\frac{7n}{10} + 6] + n$. Exactly how can I prove that this recurrence relation ...
1
vote
1answer
26 views
Comparing different asymptotic notations
Suppose we have 3 algorithms complexity times at the worst case:
A = $O(nlogn)$
B = $O(n\sqrt{n})$
C = $\Theta(n)$
In my opinion, it is not possible to define the best solution, since we don't know ...
7
votes
1answer
416 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
3answers
62 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
90 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 ...
0
votes
1answer
20 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
60 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})$$
...
4
votes
1answer
50 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
34 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
41 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
23 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
81 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
88 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
vote
3answers
73 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
72 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
62 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
31 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
26 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
57 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
29 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
39 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
33 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
101 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
84 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
56 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
72 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
65 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
22 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 ...
