Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
1,235
questions
-3
votes
0answers
10 views
asymptotic (big-O) growth and asymptotic (omega-Ω) growth [closed]
Sort all the functions below in increasing order of asymptotic (big-O) growth. If some have the same asymptotic growth, then be sure to indicate that. As usual, lg means base 2.
1)5n
1
vote
1answer
72 views
Searching in sorted array with $O(\log n)$
Recently been practicing some recent exams, there was a problem I could not comprehend the given answer, the question is as follows:
Suppose array $A[1..n]$ consist of $n$ distinct integers that is
...
0
votes
0answers
37 views
Complexity of backtracking to find power set given random array of numbers
Given an array of elements which can contain duplicates, this is an algorithm that solves the problem.
...
0
votes
1answer
23 views
Asymptotic notation for summations
I am struggling to understand why this property of asymptotic notation is true
1
vote
1answer
33 views
A monotonically nondecreasing function $ f(n) $ s.t $ f \in O(n^2) $ and $ f \notin o(n^2) $ but also $ f \in \Omega(n) $ and $ f \notin \omega(n) $
I am trying to look for an example of a monotonically non-decreasing function $ f(n) $ such that:
$ f(n) \in O(n^2) $ and $ f(n) \notin o(n^2) $ but also $ f(n) \in \Omega(n) $ and $ f(n) \notin \...
1
vote
1answer
19 views
Theta bound for runtime analysis of nested while loops
I am trying to fully analyze the running time of $\texttt{nestedLoops}$ in terms of $n$ with a Theta bound.
The Java code I have is as follows:
...
1
vote
1answer
27 views
How to solve recurrence of a binary tree
I'm trying to solve this recurrence of a function of a binary tree with a recursive tree. But I can't find any pattern to solve it.
This function calculates both the height and if its a balanced tree.
...
-5
votes
1answer
198 views
Is squaring easier than multiplication?
Let $T_1(n)$ be the time complexity of computing the square of an $n$-bit integer, and let $T_2(n)$ be the time complexity of computing the product of two $n$-bit integers.
Assuming that addition is ...
1
vote
3answers
45 views
Solving $T(n) = 2T(n/3) + T(2n/3) + n^3$
How can I solve this recursive function using substitution method?
$$T(n) = 2T(n/3) + T (2n/3) + n^3$$
I substitute $T(n/3)$ and after that $T(n/9)$. when it goes to k-step, I'm stuck.
4
votes
1answer
487 views
small o notation
Let $f$ be an $o(2^{-\sqrt n})$ function, and let $g$ be an $o(2^{-\frac{n}{2}})$ function. Is the function $ f + g - fg$ is an $o(2^{-\sqrt n})$ function?
Can you help me prove that?
I think the ...
0
votes
1answer
33 views
Sorting n weight disks with decision tree
I was refreshing some old tests about sorting algorithms, there was a question as follow:
Question: we have n weight disks with different weights and we want to ...
1
vote
2answers
50 views
Solving constants in the recursive term with master theorem
We are learning how to solve recurrence relations in different ways (Forward Substitution, Backward Substitution, Master Theorem, etc...). I really thought I understood the topic since most of the ...
1
vote
2answers
43 views
Problem in understanding big-O notation and similiar
I am trying to understand the concept of big-O notation problem and came through this problem. Can you tell me how could
$$O(n) = 1 + \Theta(1/n)$$
1
vote
1answer
60 views
Recurrence $T(n) = T(n - \log n) + 1$
Given recurrence relation : $$
T(n) = \begin{cases}
T(n-\log n) + 1 & \text{if } n \ge 1,
\\
1 & \text{otherwise.}\\
\end{cases}
$$
To find asymptotic order of $T(n)$ i do as follow:...
0
votes
1answer
42 views
Is O(1) considered polynomial time?
I am reading about P and NP and looking at the reduction of a Rudrata/Hamiltonian path to a Rudrata cycle. I think adding an extra node and 2 edges connecting the start, ...
0
votes
0answers
8 views
solving 𝑇(𝑛)=𝑇(𝑛/3)+𝑇(𝑛/6)+1 without Akra-bazzi method [duplicate]
I need to find $g(n)$ so that $𝑇(𝑛)=𝑇(𝑛/3)+𝑇(𝑛/6)+1 = \Theta(g(n))$.
I know that the recursion tree height, $h$, is $\lg_6{n}\le h \le \lg_3{n}$ and that every level of the tree has at most $2^d$...
0
votes
3answers
80 views
Solving a recurrence of uneven subproblems without Akra-Bazzi
I encountered the following recurrence relation in homework, for which we need to find its asymptotics: $$T\left(n\right)=T\left( \frac{n}{3} \right) + T\left( \frac{n}{6} \right) + 1$$
I observed it ...
1
vote
1answer
32 views
What's the time complexity of this function?
Consider the below function:
Considering that print(a) and swap(a, b) are of complexity $\theta(1)$, what is the time ...
1
vote
1answer
19 views
Which of the following is a more appropriate complexity for this reccursive function?
Given the following recurrence relation:
\begin{gather*}
h(A) =
\begin{cases}
0,\qquad \qquad \text{ }\text{ }\text{ }A=0\\
1+h(A-1),\text{ }\text{ }A\text{ is odd} \\
1+h(\frac{A}{2}),\...
1
vote
1answer
23 views
On the recurrence $T(n) = T(n/a) + T(n/b) + n^c$
Consider the recurrence
$$T(n)=T(\tfrac{n}{a}) + T(\tfrac{n}{b})+O(n^c).$$
What is the condition on $a,b$ that guarantees $T(n)=O(n^c)$?
With substitution I get
$$T(n)=T(\tfrac{n}{a}) + T(\tfrac{n}{b})...
2
votes
1answer
38 views
Binary exponentiation of matrix - complexity
I want to calculate complexity for binary exponentiation of matrix of size $k$. Let's say that I'm using the simplest approach to multiply matrices (so with three ...
0
votes
0answers
42 views
Prove or disprove $T(n) = T(\lfloor\frac{n}{2}\rfloor+1)+1=O(\log(n))$
Lets define function $T(n)$ as
\begin{align*}
T(1) &= T(2) = 1\\
T(n) &= T(\lfloor\frac{n}{2}\rfloor+1)+1 \text{, where }n\ge 3.\\
\end{align*}
Does $T(n)=O(\log(n))$? I have no idea how to ...
2
votes
2answers
43 views
How to solve recursion T(n) = T(n/3) + T(2n/3) + n?
$T(n) = T(n/3) + T(2n/3) + n$
How can I solve this recurrence formula?
1
vote
1answer
36 views
A problem about asymptotic functions
Are there two function $f:N\rightarrow N$, and $g:N\rightarrow N$ such that $f(n)+g(n)\ne O(f(n))$ $\wedge$ $f(n)+g(n)\ne O(g(n))$?
My idea: i think because of for any $f:N\rightarrow N$, and $g:...
1
vote
1answer
54 views
$O(n^2)$ running time vs $O(n^2)$ worst case
The use of the phrase "worst-case running time" is really confusing to me.
Isn't plainly stating that the time complexity of an algorithm is $O(n^2)$ supposed to mean that the growth rate of ...
1
vote
2answers
46 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 ...
1
vote
2answers
61 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 ...
1
vote
1answer
58 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(\...
-1
votes
1answer
31 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.
2
votes
2answers
34 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 ...
3
votes
1answer
31 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)} = ...
1
vote
1answer
26 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
1answer
61 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.
1
vote
1answer
44 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 ...
0
votes
2answers
55 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 ...
0
votes
1answer
26 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, $...
1
vote
3answers
54 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 ...
1
vote
1answer
20 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. ...
0
votes
1answer
18 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 ...
1
vote
1answer
37 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
2answers
100 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.
0
votes
0answers
35 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 ...
0
votes
2answers
57 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
3answers
91 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 &...
2
votes
1answer
21 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 ...
1
vote
2answers
36 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 ...
1
vote
1answer
37 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 ...
1
vote
2answers
32 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 ...
1
vote
1answer
40 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 ...
0
votes
1answer
51 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 ...
