Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
1,383
questions
0
votes
2
answers
30
views
Some questions regarding asymptotic notation of ${n \choose k}$
Is it always the case that ${n \choose k} = O(n^k)$?
If it is, then why does the comment from Clement C. in this post state it is only the case when $k$ is a constant?
If it is not, then why is the ...
- 609
0
votes
2
answers
50
views
Confusion about asymptotic notations in math and computer science
The last times i was searching a lot to understanding Big O notation or in general asymptotic notations concepts because i didnt hear about it or them before starting studying in computer science.
(...
- 3
4
votes
1
answer
55
views
Are "almost all" decidable languages not in P?
There's a famous classical circuit complexity result by Shannon that says almost all languages require exponential circuits [[1]], proven by comparing the number of distinct circuits of $n$ variables ...
- 71
2
votes
0
answers
39
views
Optimal lookup complexity when requiring insertion complexity to be at most $\mathcal O(\log\log n)$?
How can we design a data structure (storing ordered data) that gives the best worst-case lookup complexity possible, under the constraint that we require the worst-case insertion complexity to be at ...
1
vote
1
answer
56
views
Upper bounding this expression
I need to prove that the following expression is $\mathcal O(n \log n)$ with the substitution method: $$ T(n) \leq 3\log n + n + \frac{6}{n}\sum^{n - \frac{\log n}{3}}_{i=\frac{\log n}{3}} T(i)$$
This ...
- 73
1
vote
1
answer
53
views
Proving this recurrence is $n \log n$
I need to prove that $T(n)$ is $\mathcal O(n\log n)$ with the substitution method.
$$ T(n)\leq 3\log n + n + \frac{6}{n}\sum^{2n/3}_{n/3}T(i).$$
This is my attempt: I assume $T(n) \leq c n \log n$ and ...
- 73
1
vote
0
answers
51
views
Runtime of this algorithm
I have an algorithm with running time that satisfies
$$ T(n) \leq n + \frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n-i)),$$ and $T(0) = 0$. I was able to show that $T(n) = \mathcal O(n\log n)$ with a leading ...
- 247
0
votes
3
answers
47
views
Using limits to determine asymptotic bound
By using limits, show that log n! ∈ Θ(n logn).
Using Stirling's approximation for n! I get the limit:
$$\lim_{n \to ∞} \frac{log({\sqrt{2πn}}*(\frac{n}{e})^n)}{nlogn} = constant > 0$$
When I break ...
- 3
0
votes
1
answer
33
views
Understanding why this upper bound is tight
Consider an algorithm with the following recursion $$ T(n) \leq T(n/3) + T(2n/3) + \mathcal O(n)$$ for its running time. I understand that $T(n) = \mathcal O(n \log n)$ by drawing the recursion tree ...
- 247
0
votes
2
answers
58
views
Asymptotic Relationship between 1/n and 1/2^n
What is the asymptotic relationship between $\frac{1}{n}$ and $\frac{1}{2^n}$?
The answer here mentions that both functions are $O(1)$ (because they are always $\leq 1$) but not $\Omega(1)$ (because ...
- 11
0
votes
0
answers
24
views
Solving a recurrence relation using the Master Theorem
I'm trying to solve this recurrence relation:
$T(n) = T(\frac{n}{2}) + T(\frac{n}{5}) + T(\frac{n}{10}) + c_1n$ ; n > 1
$T(n) = c_2n$ ; n = 1
My first thought was to combine the fractions and ...
user154475
1
vote
0
answers
63
views
Is it true that: $f\notin o(g)$ implies $\exists c>0: f > cg$ infinitely often
My (attempt at a) proof is as follows:
$f\in o(g)$ means that $\forall c>0 \exists n_0 \forall n\geq n_0: f(n) \leq cg(n)$.
Now taking the complement we get: $\exists c>0 \forall n_0 \exists n\...
- 11
4
votes
1
answer
89
views
Optimal algorithmic complexity of "a nonrepetitive stack"?
I'm wondering about the optimal complexity - or at the very least, some way of achieving non-terrible complexity - of a particular stack variant, that I'm calling a 'nonrepetitive stack'.
A ...
- 1,319
0
votes
0
answers
39
views
Can 0 be a tight upper bound of -4n?
I'm newbie in algorithm time complexity.
I had a function, f(n) = 2n2 - 4n.
I have to proof that f(n) = O(n2).
We can take it ...
0
votes
0
answers
26
views
Proving an asymptotic bound with induction
Suppose we want to prove by induction that $f(n) \in \Theta(g(n))$. How should the induction proof be set up? I'm tempted to say that the base case should prove that $f(1) \in \Theta(g(1))$ and the ...
- 247
11
votes
3
answers
2k
views
Is Big-Theta a more accurate description of worst case run time than Big-O?
Question I was asked: Does it make a difference if I say "The worst case run time is $O(n^2)$ vs the worst case run time is $\Theta(n^2)$?"
To me, the only difference is that when we say $O(...
0
votes
2
answers
61
views
What is the asymptotic runtime of the below equation?
What is the asymptotic of
${n \choose 3} \log ^4n$ ?
I know that ${n \choose 3}$ is in $\cal O (n^3)$, but what about the term $log^4n$ and what about the product of the two?
- 135
0
votes
0
answers
21
views
Time complexity of Trie autocompletion (multiple variables in time complexity)
I am trying to understand what the time complexity for an autocomplete function for a Trie-based dictionary would be. Every node contains a letter and whether it is the last letter of a word, and if ...
- 1
0
votes
0
answers
14
views
How to compare two functions which themselves contain additions/subtraction between two functions?
I'm new to Asymptotic Notation and wanted to know how to compare two functions which contain sub functions or contain addition/subtraction of other functions.
For example : f(n) v g(n), where f(n) = a(...
0
votes
2
answers
87
views
Is $n=\Theta(n^{1+o(1)})$?
Is $n=\Theta(n^{1+o(1)})$?
To me it appears to be true as $n$ tends to infinity $n^{o(1)} =0$.
- 35
1
vote
1
answer
56
views
Solve the recurrence $T(n)=T(\frac{n}{2})+\frac{n}{\log n}$ without master theorem
Suppose given the recurrence $$T(n)=T(\frac{n}{2})+\frac{n}{\log n}.$$
I think the answer is
$$T(n)=O\left(\frac{n}{\log n}\right).$$
because
$$T(n)=T(1)+\sum_{i=0}^{\log n-1} \frac{n}{2^i(\log n-...
- 11
-3
votes
1
answer
55
views
Prove f(n) = o(g(n)) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n))
How can I prove this: f(n) = o(g(n)) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n)) ?
- 1
1
vote
0
answers
37
views
Algorithms with different upper and lower bounds
I am preparing a list of algorithms for which big theta expression for (worst case) runtime is not known. This is for a class to demonstrate the point that tight analysis of an algorithm may not be ...
- 11
0
votes
2
answers
43
views
If $f \in \mathcal{o}(g)$, does $f \circ g \in \mathcal{o}(g \circ f)$?
It's a widely known fact that $\lambda n. \left\lfloor \lg n! \right\rfloor \in \mathcal{O}(\lambda n. \left\lfloor \lg n \right\rfloor!)$. Is it also true (I tried and haven't found a counterexample ...
- 115
0
votes
1
answer
66
views
Complexity of multiple $O(\log N)$ is $m*O(\log N)$ or $O(\log N)$?
Assume we have an algorithm consists of several (assume m and m<10) different algorithms each of which has time complexity $O(\log N)$. Is the time complexity of our algorithm is $m*O(\log N)$ or ...
- 151
1
vote
1
answer
63
views
Difference between "almost-linear" and "quasilinear" time complexities
In some works, such as the recent maxflow paper, there is reference to an "almost-linear" complexity, which typically refers to a complexity of $O(n^{1+o(1)})$.
This is similar to the notion ...
- 43
1
vote
1
answer
39
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 ...
- 11
1
vote
0
answers
34
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
48
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
57
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
319
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
621
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
...
- 379
0
votes
0
answers
79
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
75
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
52
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
36
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
367
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
49
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
37
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 ...
- 57
2
votes
1
answer
62
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
53
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
92
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 ...
- 578
1
vote
0
answers
50
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 ...
- 578
3
votes
1
answer
87
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
57
views
Which approach of mine for an algorithm upper bound is correct?
Say we have this algorithm in Python.
...
- 133
1
vote
1
answer
45
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
39
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
79
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 ...
