Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
1,357
questions
0
votes
2
answers
22
views
Contradicting asymptotic analysis in recurrence equation?
I'm trying to solve the recurrence equation from CLRS ed 2.
$$
T(n) = 2T(\sqrt{n}) + 1
$$
The question says the solution should be asymptotically tight, but at first I didn't read it and solved it ...
1
vote
0
answers
24
views
Does creating an array count as a primitive operation under the RAM model?
int[] arr = new int[10];
Would this count as a single primitive operation under the RAM model or would it be 10 operations as we are allocating 10 memory locations ...
- 11
0
votes
1
answer
35
views
Solve Recurrence T(n) = 4T(n/4) + n*[log(n)]^2
I am trying to solve
T(n) = 4*T(n/4) + n*[log(n)]^2
I decided to use Master Theorem so I found a,b=4 and logb(a)=1.
I thought that 3rd case is the solution but I ...
0
votes
2
answers
47
views
A little confusion with Big Theta time complexity
I came across one Big Theta expression:
Here I am thinking this expression to be valid. But please correct me as the answer doesn't goes in the same way.
As per definition of Big Theta.. any function ...
3
votes
2
answers
302
views
Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails
Given the algorithm
MYSTERY-ALG(n >= 0)
1 if n < 3 then
2 return 1
3 else
4 return MYSTERY-ALG(n/2) + MYSTERY-ALG((n/2) + 1)
I defined a recurrence
$ ...
- 45
2
votes
2
answers
613
views
An α-good tree with n nodes has height O(log n)
Let $α \in [0, 1)$ be a constant. For a rooted binary tree $T$ and a node $x$ in $T$, we denote by
$|x|$ the number of nodes in the subtree of $T$ rooted at $x$ (if $x$ = $NIL$ then $|x|$ = $0$). We
...
- 369
1
vote
0
answers
27
views
Worst case lower bound of the general number guessing problem
I have the following problem:
Let Alice and Bob be two people playing games.
Alice and only Alice owns a special device, Robo, that is capable of generating one truly random number $k \in \mathbb{N}$ ...
1
vote
4
answers
72
views
Why is $a^{\log_b n}$ the same as $n^{\log_b a}$?
I was watching video Lec 2 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005, where professor Erik Demaine said that $a^{\log_b n}$ is the same as $n^{\log_b a}$. Can someone ...
0
votes
1
answer
51
views
equivalency of some facts in $O$ notation
I misunderstanding about some logarithm property in algorithm course:
is it correct that we say following three term is equivalent?
$O(\log a + \log b)$
$O(\log (ab))$
$O(\log (a+b))$
- 381
0
votes
0
answers
26
views
The total number of nodes and the height of a ternary search tree
So I need to insert into the ternary search tree (TST) about N strings. Each string is a unique ID "consists of 10 letters, the first 3 are upper case letters and the last 7 are digits" for ...
3
votes
2
answers
313
views
Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n
Given the recurrence
$$T(n) = 2T\bigg(\frac{n}{8}\bigg) + 2T\bigg(\frac{n}{4}\bigg) + n$$
My professor says that $T(n)$ is $O(n\log n)$ but I have calculated a complexity of $O(n)$ as shown below with ...
- 337
1
vote
1
answer
46
views
Simplifying Notations in Recurrence Relation
In the CLRS book, section 4.4 they try to resolve the following recurrence:
$$T(n) = 3T\bigg(\bigg\lfloor \frac{n}{4} \bigg\rfloor\bigg) + \Theta(n^2)$$
Later, they write the same recurrence as
$$T(n) ...
- 212
1
vote
1
answer
32
views
Comparing two functions rate of growth
This is pretty simple and I THINK I know the answer to the question, but I don't know how to prove it formally. Below follows the question.
Question. Compare the functions $f(n) = \frac{n^2}{\log(n)}$ ...
- 187
-2
votes
2
answers
57
views
Prove $n\log n\neq O(g(n))$ where $g(n)$ alternates between $\log^*n$ and $n!$
I have to prove that $f(n) \neq O(g(n))$, where $f(n) = n\log n$ and $g(n)$ is $\log^*n$ if $n$ is odd and $n!$ if even.
So my thought is to say that $f(n) = O(g(n))$ and then with the definition ...
- 47
2
votes
1
answer
56
views
Trying to understand the basic about recurrence trees
I have little background on recurrence trees, and I am working on the following exercise:
Exercise. Take $T(n) = 2T(n/2) + 3\log(n)$. Draw the recurrence trees for $n=2$ and $n=4$. What can we ...
- 187
1
vote
3
answers
48
views
A function which is both $o(\log^* n)$ and $\omega(1)$
I've been trying to find a function $T(n)$ whose asymptotic rate of growth satisfies both of the following conditions:
$T(n)= o(\log^*n)$
$T(n)= \omega(1)$
But I can't think of a function with this ...
- 11
3
votes
2
answers
67
views
Linearity property of summation applied to Big Theta notation (CLRS math background appendix)
Section A.1 of the Mathematical Appendix of the CLRS, the third edition, page 1146, contains the following formula stating linearity property of summation applied to $\Theta$ notation:
$$
\sum_{k=1}^{...
0
votes
1
answer
22
views
How do I get $T(n) \leq 3T(\lfloor n/4 \rfloor) + cn^2$ from $T(n) = 3T(\lfloor n/4 \rfloor) + cn^2$?
Section 4.4 of Introduction to Algorithms, 3rd Edition
By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein gives the following to verify that $O(n^2)$ is an upper bound for ...
- 576
1
vote
0
answers
38
views
Given T(1)=1 and $T(n) = 3T(n/4) + cn^2$, does it make sense to yield $T(2)=T(1)+c2^2$?
Section 4.4 of "Introduction to Algorithms, 3rd Edition
By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein" illustrates how a recursion tree provides a good guess ...
- 576
3
votes
1
answer
71
views
Find the flaw in the 3SAT solver algorithm
I consider decision version of 3SAT problem.
Main idea is to find congruent clauses and construct such maximum formula,
which satisfiability/truth table won't be changed.
In case of unsatisfiable ...
- 199
2
votes
1
answer
55
views
Which approach of mine for an algorithm upper bound is correct?
Say we have this algorithm in Python.
...
- 133
1
vote
1
answer
38
views
Newbie needs some explanation on the following code and O-expressed time complexity
I am learning data structures and algorithms currently, and want to understand how the following codes received their O-notations.
Code example #1:
...
- 113
1
vote
1
answer
36
views
Find the proper hypothesis for the substitution method for a recurrence problem
I'm trying to solve a recurrence problem using substitution method:
Given the following recurrence equation:
$
T(n) =
\begin{cases}
3 &n = 0 \\
3T(\frac{n}{5}) + T(\frac{n}{6}) + n&n ...
- 165
1
vote
0
answers
77
views
Recursive algorithm running time?
I would like your opinion on how to detect the T(n) (Running Time) for the following recursive algorithm.
Charm is an algorithm for discovering frequent closed itemsets in a transaction database. A ...
-1
votes
2
answers
83
views
Which is larger: $n^{3/2}$ or $n^{\log n}$?
We know that $f(n)$ is $\mathcal O(g(n))$ if $\exists c\ge0$ s.t. $$\lim_{n\to\infty}\dfrac{f(n)}{g(n)} = c.$$
Let $f(n)=n^{3/2}$ and $g(n)=n^{\log n}.$
When I am applying L'Hôpital's rule for $$\...
- 1
1
vote
1
answer
35
views
In the theta notation definition, is it possible that $n_0$ could equal 0?
This is the definition of theta notation:
The function $T(N)$ is $\Theta(g(N))$ if there exist positive constants $C_1$, $C_2$ and $N_0$ such that $C_1g(N) \le T(N) \le C_2g(N)$ for all $N \ge N_0$.
...
- 185
1
vote
1
answer
35
views
Tight analysis on a custom data structures with Insert and Remove-Min
I have a data structure supporting the operations Insert(X) and Remove-Min(). Remove-Min() ...
- 149
0
votes
0
answers
37
views
Proving transitivity of big-omega and big-theta notations
I am trying to understand mathematical proofs and their applications to big-omega $\Omega$ and big-theta $\Theta$ notations.
The first one is transitivity:
$f \in O(g) \; and \; g \in O(h) \Rightarrow ...
- 1
1
vote
1
answer
91
views
Time complexity of an algorithm in the $\Theta$ notation
Consider the following algorithm:
res := 0
for i := 1 to n do
j := i
while j mod 2 = 0 do
j := j / 2
res := res + j
What's its time complexity ...
- 13
4
votes
1
answer
361
views
Big O vs. Big Theta for AVL tree operations
On the Wikipedia page for AVL trees, the time/space complexity for common operations is stated both for average case (in Big Theta) and worst case (in Big O) scenarios. I understand both Big O and Big ...
- 43
0
votes
1
answer
44
views
Do tasks that take up more memory/space always take more time?
Apologies if this is a trivial question - but I can't seem to find a direct answer to this. Say program A manipulates some data, and program B does the same manipulation, except it operates on a deep ...
- 113
-3
votes
1
answer
55
views
Solve the recurrence $3T(n) = T(n/3)+ \sqrt{\log n}$
How can you solve the recurrence $$3T(n) = T(n/3)+ \sqrt{\log n}$$ using the master theorem?
I am lost in this question.
- 1
1
vote
1
answer
81
views
Prove recurrence T(n) = 2T(n/2) + n/lgn is O(nlglgn) using Substitution Method
Prove that $T(n) = 2T(\frac{n}{2}) + \frac{n}{\log_2n}$ is $O(n\log_2\log_2n)$, where $T(1) = Θ(1)$.
I tried to form the Induction Hypothesis but didn't succeed in choosing the right one.
Try 1:
If we ...
- 45
1
vote
1
answer
27
views
How can we assume the asymptotic complexity of 1/2n^2 - 3n
I am trying to understand how asymptotic complexity of the given function is calculated based out of Introduction to algorithms by Thomas Cormen.
In the book we are trying to solve inequality for $f(n)...
3
votes
1
answer
103
views
Analytic combinatorics and less-precise running times
Analytic combinatorics and concrete mathematics are the mathematics of asymptotic counting, and they draw from combinatorics, analysis, and probability. These techniques have been applied to the ...
- 315
5
votes
3
answers
145
views
Asymptotic of $\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}$
I'm trying to figure out the asymptotic estimate of $\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}$. I think it is $\omega(2^{\sqrt{n}})$ and am trying to prove it by showing $\lim_{n \rightarrow \infty} \...
- 53
0
votes
0
answers
28
views
Why are we allowed to ignore constant factors of $g(x)$ in recurrence while they are important in solving the recurrence?
I'm trying to learn about asymptotic notations and recurrences and I use MIT 6.042 Mathematics for Computer Science as my resource. and I have some questions about the Professor's talks.
He said:
...
- 1
1
vote
3
answers
50
views
Will Big Theta not apply when $f(n)$ and $g(n)$ are of different order?
I'm currently taking my algorithms class, and I learnt that Big theta is defined as follows:
$f(n) = \Theta(g(n))$ if there exist constants $c_1, c_2, n_0 > 0$ such that $0 ≤ c_1g(n) ≤ f(n) ≤ c_2g(...
- 21
1
vote
2
answers
93
views
Solve the recurrence equation $T\left(n\right)=\sqrt{n}\cdot T\left(\sqrt{n}\right)+c\log n$
I tried to solve the recurrence $T\left(n\right)=\sqrt{n}\cdot T\left(\sqrt{n}\right)+c\log n$ using the Master Theorem. I tried the following way:
$n = 2^k$
$2^{\frac{2}{k}}\cdot T\left(2^k\right)+\...
- 29
0
votes
2
answers
90
views
n! and 2^(n^2); which one grows faster
I can't figure this out; is $2^{n^2}=O(n!)$ or is it the other way around? Any help is appreciated!
- 105
1
vote
1
answer
78
views
Subtraction on Big Theta notation
This is a question I got for an assignment, and I have been stuck on it for the past few days.
Prove that
$\Theta(n)+\Theta(n-1) = \Theta(n)$
Does it follow that $\Theta(n) = \Theta(n)-\Theta(n-1)$
I ...
- 11
0
votes
0
answers
27
views
Sum of asymptotic notations
Let's consider a function $f \in \Theta(h)$ and a function $g \in \omega(h)$, what could I conclude about the sum $f + g$?
Since $f \in \Theta(h)$ I think about $f$ as if it grows just like the ...
- 13
1
vote
3
answers
126
views
Θ, O and Ω, and how they relate to each other as subsets
I am trying to understand how $\Theta(n)$, $O(n)$, and $\Omega(n)$ relate to each other as sets and want to make sure I'm on the right track.
I get that $Θ(n) \subseteq O(n)$ since $Θ(n)$ is stronger ...
- 11
1
vote
1
answer
48
views
What would be the correct asymptotic lower bound for $f(n) = 3n^2 + 2n$?
What is the correct asymptotic lower bound for $f(n) = 3n^2 + 2n$?
I was thinking that the lower bound would simply be $\omega(n) = cn^2 + n$, for the constant $c = 3$ and integer $n \ge 1$. Indeed, $...
2
votes
1
answer
94
views
Asymptotic height of d-ary heap
I know that the height of a $d$-ary heap on $n$ nodes is $\lceil (\log_d (n(d-1) + 1) - 1)\rceil$, but I was wondering how to justify that that's $\Theta(\log_d n)$?
I know the definition of $\Theta, ...
- 225
0
votes
1
answer
29
views
Sum of a function Θ(g) with a function that is not O(g)
Consider g a function of n: $g(n)$.
Knowing that the function $f(n) \in Θ(g(n))$ and the function $h(n) \notin O(g(n))$, could we conclude anything, related to it's asymptotic behaviour, about $f(n) + ...
- 13
0
votes
0
answers
48
views
Time complexity of this for-loop
I know, the inner loop here is O(log n). But, I get confused by the multiplication in the outer loop part.
...
- 125
-1
votes
1
answer
113
views
Why is $n^{1.98}$ an element of $O(n^2)$?
Why is option "(C) $n^{1.98}$ is $O(n^2)$" the question below correct? Is it because "Big $O$" is upper bound meaning worst case, therefore $n^{1.98}$ is not worst case $n^2$ ?
How ...
1
vote
1
answer
31
views
Comparing order of growth with n^(logn) - need to know where value comes from?
I'm trying to understand how you compare the following for order of growth.
With the below working out with $f_4$ I don't get where the $x^5$
and $x^6$ come from at the end. With $f_4$ you have $n^{\...
0
votes
2
answers
72
views
Is log^2 (n) ∈ O(n) true?
I'm new to algorithm, and I am already overwhelmed with the term ∈ I really could use some good explanation.
