Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
1,453
questions
1
vote
2
answers
57
views
Asymptotic bounds of the following operations
I have a very simple question about the best possible big-O bounds for the following data structure:
It starts out empty When you add an element, it is inserted, and the index it was at is associated ...
- 235
1
vote
2
answers
106
views
Lower bound $\Omega$ grows quicker than upper bound $O$ of a recurrence relation $T(n)$?
In my analysis of algorithms class we were given the following recurrence relation:
\begin{eqnarray}
T(n) &=&
\begin{cases}
T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is ...
- 13
0
votes
2
answers
103
views
How to find infinite set $X$, which satisfies $T(n)=Ω(n)$ when $n∈X$
Consider the following recurrence relationship.
\begin{eqnarray}
T(n) &=&
\begin{cases}
T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is even number}& \\
2T\left(\...
- 155
-1
votes
1
answer
70
views
Asymptotics of harmonic series [closed]
Show that $$ 1 + \frac{1}{2} + \cdots + \frac{1}{n} = \Theta(\ln n) $$
How do I solve this problem?
I tried to to integrate it but I got a weird answer.
- 9
2
votes
2
answers
296
views
How to solve $T(n)= T(n - 1) + \frac{1}{n\log n}$?
I am interested in the asymptotic bounds of the following recurrence:
$$T(n)= T(n - 1) + \frac{1}{n\log n}$$
with base case $T(1) = 1$. I'm having trouble while solving this recurrence. It seems much ...
- 23
3
votes
1
answer
45
views
Asymptotic complexity of $-\log(c^{1/n} - 1)$
What is the asymptotic complexity of
$$f(n) = -\log(c^{1/n} - 1)$$
for some constant $c > 1$? I conjectured $O(\log n)$ and checking WolframAlpha does give $$\lim_{n\to\infty}\frac{f(n)}{\log(n)} = ...
- 13.4k
1
vote
1
answer
108
views
Multiple Variables in Asymptotic Notation
I am trying to understand the multiple variable definition of an asymptotic notation. Particularly the definition in Wikipedia. It's also discussed in Asymptotic Analysis for two variables? but I ...
1
vote
1
answer
112
views
Is $𝑂(𝑛^{1/2}) = \Omega(𝑛^{\sin(n)})$?
As $-1 <\sin(n) < 1$, So $n^{\sin(n)}$ is bounded, but square root of $n$ tends to infinity. Is my logic correct? But from the other perspective, $1/n \leq n^{\sin(n)} \leq n$. I am confused.
- 25
1
vote
1
answer
197
views
Which grows asymptotically faster, $\log \sqrt{n}$ or $4 \log n$?
I have been looking at the question as to which grows faster asymptotically; $\log \sqrt n$ or $4 \log n$. I have applied L'Hopitals rule and ended up with 1/8. This would imply that they grow at ...
- 19
0
votes
2
answers
89
views
Is $n^2 \log n$ in $O (n^2)$ am confused
I graphed the functions and when $n_0$ is greater than $3$, $cg(n)$ is always greater than $n^2 \log n$ so it would seem to me by definition that $m^2 \log n$ is in $O (n^2) $. I tried to prove it by ...
- 19
0
votes
1
answer
77
views
Can you add up all the nodes of a special binary tree in polynomial time, in respect to the number of levels?
Let's say you have a binary tree defined by a group $S=\{a:[5,6],b:[7,67],c:[45,12],...\}$ (this group is just an example). The binary tree is constructed so that there are two starting parent nodes, $...
- 289
1
vote
3
answers
206
views
Big Oh and Big Omega when $n$ and $\log n$ terms are in $f(n)$
having problems with big oh and big omega functions when there is a $\log n$ added or subtracted. For example how do I deal with $n+\log n$ or $n-\log n$ when I have to determine whether the function ...
- 19
1
vote
1
answer
71
views
Computational indistinguishability for any distribution using a Chernoff bound
I had a question about a general statement regarding finding a computationally indistinguishable distribution given any distribution, observed (in the third paragraph of Section 11, page 31) here. ...
- 249
1
vote
3
answers
94
views
What are the guidelines/tips for calculating the complexity of a chained-recursive function?
Any help will be appreciated, as I wasn't able to find much about it online in the last few days and I can't seem to write a suitable recurrence relation for this kind of functions..
Are there any ...
- 11
2
votes
1
answer
227
views
Master theorem: $T(n)=10T(n/9)+n\lg(n)$
I am told to solve the recurrence
$$T(n)=10T(n/9)+n\lg(n)$$
using the Master theorem. I then try to use case 3. However, I am unable to show that for $f(n)=n\lg(n)$ then $10f(n/9) \leq cn\lg(n)$ for $...
0
votes
2
answers
276
views
Average case running time of quick sort
How to show that the quick-sort algorithm runs in $O(n^2)$ time on average ?
Because on average, the expected running time is in $O(n\log n)$. The algorithm should not be in exponential time.
- 11
0
votes
0
answers
47
views
Adding $\Theta$ notations in a recursive setting
I know the fact that if we have two functions $f$ and $g$ it is valid to say that:
$$ \Theta( f(n) + g(n)) = \Theta( \max\{f(n), g(n)\})$$
My question is if this is valid when $g$ is not a separate ...
1
vote
3
answers
5k
views
Solving recurrence $T(n) = T(n - 1) + n$ with substitution method
How can I solve the following recurrence $T(n) = T(n - 1) + n$ with the substitution method?
I guess the solution is $\Theta(n^2)$ I try to demonstrate $O(n^2)$:
$$T(n) \leq O(n^2) \\ \leq c(n-1)^2+n ...
0
votes
3
answers
158
views
Does exponential time always beat polynomial time? $n^{\frac{1}{2}}$ vs $2^{\sqrt{log \,n}}$
I was told that exponential time always beats polynomial time but doesn't this not work for:
$n^{\frac{1}{2}}$ vs $2^{\sqrt{log \,n}}$?
If we take $log_2$ on both of them we get:
$\frac{1}{2}log \,n &...
- 659
2
votes
1
answer
33
views
Proving bounds for a function
I'm kinda confused by Asymptotics, the exercises in the book I'm reading say to prove for example $f(n) = \Omega(g(n))$, and there is something I don't understand about these kind of proofs.
Do I have ...
- 235
1
vote
2
answers
139
views
Constant terms at each level of a recursion tree
In CLRS, exercise 4.4-5 the following question is asked:
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $$T(n) = T(n-1) + T(n/2) + n$$
In my recursion tree, the ...
- 123
1
vote
1
answer
426
views
Proving big-theta complexity with constants in $f(n)$
I am working through a problem in which I have to prove that a particular $f(n) = \Theta(g(n))$. I know that for this to be true there need to exist positive constants $c_1$, $c_2$, and $n_0$ such ...
2
votes
2
answers
660
views
Big theta notation in substitution proofs for recurrences
Often in CLRS, when proving recurrences via substitution, $\Theta(f(n))$ is replaced with $cf(n)$.
For example, on page 91, the recurrence
$$ T(n) = 3T(⌊n/4⌋) + \Theta(n^2) $$
is written like so in ...
- 21
1
vote
1
answer
78
views
Problem from the Cormen appendix C 1.13
I am currently working on CLRS 1.13. The idea is to use Stirling's
approximation to prove that
$${2n \choose n} = \frac{2^{2n}}{\sqrt{\pi n}} \left( 1 + O \left( \frac{1}{n} \right) \right)$$
Now ...
- 149
0
votes
1
answer
71
views
$\Theta(n^2 ) =\Theta(n^2 + 1)$
I'm reading The Algorithm Design Manual and this is one of the excersizes:
Prove or disprove the following statement:
$\Theta(n^2 ) = \Theta(n^2 + 1)$
I think this is untrue because the right side ...
- 235
0
votes
1
answer
698
views
Is big O notation additive?
For example, I have one program that requires $O(i)$ time complexity, and a second program requires $O(j)$ time complexity. Would the total time complexity be $O(i+j)$? And why?
- 215
3
votes
2
answers
17k
views
Calculator for time complexity of recursive functions
Is there an online tool that returns the time complexity of recursion functions?
For instance, when I enter $T(n) = T(n/2) + n$, I'd like to get $\Theta(n)$.
I tried using Wolfram Alpha, but it doesn'...
- 165
1
vote
1
answer
360
views
How to check if an algorithm's running time is linear/polynomial in its input size? Multiple variables
I am reading a proof that the Subset Sum decision problem is NP-complete.
I know that the time complexity is always calculated based on the number of bits of the input in binary, hence the $\log{W}$.
...
- 108
1
vote
1
answer
872
views
Time complexity and upper and lower bounds
Consider the following algorithm:
(the print operation prints a single asterisk; the operation x = 2x doubles the value of the ...
- 235
1
vote
2
answers
64
views
Operations with Asymptotic Notations
I am wondering is anyone has something like a cheatsheet with all the operations between $O(n)$, $\Theta(n)$, $\Omega(n)$, $o(n)$, $\omega(n)$. For example, this is something I don't know how to solve:...
1
vote
1
answer
72
views
Asymptotic notation between two sets of variables
I have problems interpreting the definition of asymptotic notation where the functions involve two different set of variables. I am quite confident with the definition of $f(n) = O(g(n))$ and its ...
1
vote
1
answer
271
views
Counting letter frequency in array in O(1) with hash function
I want to calculate the frequency of each character in an array. (e.g ['a', 'b', 'o', 'p']
There are several ways to do this:
A Simple brute-force over the array would need $O(n^2)$ time and $O(n)$ ...
- 167
1
vote
3
answers
134
views
Ω(f(x)) and worst case analysis
I'm currently reading The Algorithm Design Manual by Steven S. Skiena as my first book to algorithms.
Something in the asymptotic part is kind of confusing to me.
Proving the Theta
The analysis above ...
- 235
2
votes
2
answers
570
views
Trouble finding average case of a find max algorithm
I'm trying to find the average case number of times that max is assigned by the algorithm findMax included below.
...
- 23
1
vote
1
answer
125
views
The Algorithm Design Manual - Working with the Big Oh
I'm reading The Algorithm Design Manuel and one part is kind of confusing to me
The part that's confusing to me is how in the "Proving the Theta" section he proves that selection sort is Ω(n^...
- 235
1
vote
1
answer
1k
views
Solving the recurrence $T(n)=T(n-2)+n^2$ with the iterative method
I'm trying to solve this recurrence. I applied the iterative method:
$$T(n) = T(n-2)+n^2$$ $$=T(n-4)+(n-2)^2+n^2$$ $$=T(n-6)+(n-4)^2+(n-2)^2+n^2$$ $$\cdot$$$$\cdot$$$$\cdot$$ $$=T(n-2k) + \sum_{i=0}^{...
0
votes
1
answer
114
views
Finding the Big-O and Big-Omega bounds of a program
I am asked to select the bounding Big-O and Big-Omega functions of the following program:
...
- 213
4
votes
2
answers
273
views
Finding which functions are bounded by $O(n^2)$
I am asked to select the functions that are bounded by the Big-Oh function O(n^2): $f(n) \in O(n^2)$.
$f(n) = \sum_{i=1}^{n} n$
$f(n) = \sum_{i=1}^{n} i$
$f(n) = n + n^2$
$f(n) = 1$
I choose the ...
- 213
-2
votes
2
answers
188
views
Is there a real life example of algorithm that has running time $\Theta(1)$
I am a CS first year student, and as I was reviewing over the theta notation unit, I saw that $\Theta(1)$ exists. I was wondering if there was any real life example algorithm that has a running time ...
- 3
2
votes
2
answers
81
views
Big Oh rules - How to argue in case of negative base
Let us say you have a function $C_n = (-2)^n + 2^n$.
It would seem that it would be correct to assume that the running time of this algorithm would be $O(2^n)$.
However, how would I go about arguing ...
1
vote
1
answer
40
views
Comparison of $(\log^* n)!$ and $(n\log n)^b$ [duplicate]
How can I compare $(\log^*n)!$ with $(n\log n)^b$?
I know that $n^b<n!$.
- 21
0
votes
2
answers
493
views
Worst case analysis of $100n + 5$ for different $n$
For the function $f(n) = 100n + 5$, what is the asymptotic complexity of $f(n)$ in terms of Big O notation. I guess it is $O(n)$, but how can I prove it ?
Omer
1
vote
1
answer
4k
views
Solving $T(n) = 4T(n/2) + n^3$ with substituton method
I am trying to solve the following recurrence $T(n) = 4T(n/2) + n^3$ with substitution method. My guess is $T(n) = \Theta (n^3)$ (I used master theorem) and I tried to show that $T(n) \leq cn^3$. But, ...
8
votes
2
answers
2k
views
Isn't linear time O(n)?
In the question in this video about quicksort luckily picking the median in each recursive call. Tim Roughgarden, the presenter, says at 11:22
Partition needs really linear time, not just $O(n)$ time....
- 659
2
votes
1
answer
453
views
Comparing two algorithms for all-pairs shortest paths
I read in my notes:
If we use Dijkstra $|V|$ times ($|V|$ number of vertices) for finding all-pairs shortest paths in graph $G$, we get time complexity for Dijkstra algorithm as $O(VE+ V^2 \log V)$, ...
- 31
0
votes
1
answer
45
views
Doing induction on recurrences correctly
I have $$T(n)=T(n-1)+n^{2}$$
And I know, by drawing the recursion tree that this is $\Theta (n^{3})$
However, if I try claiming that it's $O(n^{2})$ through induction:
$$T(n)\le c(n-1)^{2}+n^{2}\le cn^...
- 155
1
vote
1
answer
49
views
Solving $T(n)=3T(\lfloor \frac{n}{3}\rfloor) +2n\log n$
I want to solve $$T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n,$$
with base case $T(n) = 1$ if $n \leq 1$.
I am sure that the Master Theorem does not work. I am trying a lot with ...
- 147
0
votes
1
answer
102
views
Recurrence relations and induction: guessing the right bound
I'm currently dealing with the problem $$T(n)=T(\sqrt{n})+T(n-1)+n$$
This doesn't seem to show any pattern when continously broken down as a whole, but I was able to find the complexity of $$T(n)=T(n-...
- 155
0
votes
2
answers
89
views
Failing to solve a recurrence by induction
My question is strongly related to the one asked here:
How do I show T(n) = 2T(n-1) + k is O(2^n)?
$$T(n)=2T(n-1)+1$$
Going with the steps, I reached the point where:
$$c*2^{n}\geq c*2^{n}+1$$
which ...
- 155
-2
votes
1
answer
2k
views
Solving $T(n) = 16T(n/2) + n$
I am trying to solve the following recurrence relation :-
$T(n)=16T(n/2)+n$ using masters theorem. I got $\Theta (n^2)$ (Which matched the first case in the theory) which is wrong, any help with this ...
