Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.

learn more… | top users | synonyms (1)

1
vote
0answers
20 views

Asymptotic expansion of a Laplace-type integral with a “manifold of maxima”

Consider the integral $$ I(\alpha)=\int_0^1 dx_1 \int_0^1 dy_1\int_{x_1}^1dx_2\int_{y_1}^1dy_2\,e^{-\alpha(x_2-x_1)(y_2-y_1)} $$ in the limit $\alpha\rightarrow\infty$. To find the asymptotic ...
2
votes
1answer
15 views

Estimate of tails of sums of reciprocals of a bit more than powers

The tails of sums of reciprocal powers have nice estimates: For $\alpha>1$ the integral test gives $$ \sum_{n=j}^\infty \frac{1}{n^\alpha} \leq \int_{j-1}^\infty \frac{1}{x^\alpha} dx = ...
1
vote
0answers
28 views

How would you prove this Big Omega complexity?

We're given $f(n)=\frac{1}{5}n^2-30n-5$ and $g(n)=n^2$, and are asked to prove $f \in \Omega(g)$. The exercise was posted, but no solution is given (this is not an assignment question). So by ...
4
votes
7answers
442 views

Is it true that $2^n$ is $O(n!)$?

I had a similar problem to this saying: Is it true that $n!$ is $O(2^n)$? I got that to be false because if we look at the dominant power of $n!$ it results in $n^n$. So because the base numbers are ...
3
votes
0answers
36 views

Applying function to both sides of asymptotic expression

I apologize in advance if this has been asked elsewhere, but I couldn't find it. This seems like it should be a pretty simple question, but I'm drawing a blank. If you know that $f(x) \sim g(x)$, ...
1
vote
3answers
50 views

Big-O notation examples

How do I get c = 4 and n0 = 21, I understand that I could plug in different numbers till f(n) ≤ c * n for all n ≥ n0, but using f(n) how do I arrive at those numbers? ...
12
votes
2answers
245 views

When is this sum of perfect powers bounded

For any positive integers $n,d$, let $$ A_d(n)=\frac{\sum_{k=1}^n k^{2d}}{n(n+1)(2n+1)} $$ It is easy to see (and well-known) that for fixed $d$, $A_d(.)$ is a polynomial of degree $2d-2$. Writing ...
1
vote
2answers
44 views

Probability that colored balls are separated

Say we throw $b$ blue balls and $r$ red balls uniformly into $n$ boxes. The probability that no box contains a red as well as a blue ball is then, by the inclusion exclusion principle: $$p = ...
0
votes
1answer
17 views

Counting Primitive Operations

This is the solution I've been given for counting primitive Operation in an algorithm. I think I have my head around how all the operations are found, for instance the 2(n-1), the 2 is the primitive ...
1
vote
1answer
125 views

Theta notation from $\DeclareMathOperator{\lg}{lg}$the inequality $c_1\lg(n) \leq \lg(k) \leq c_2\lg(n)$

Consider the inequality $$ c_1\lg(n) \leq \lg(k) \leq c_2\lg(n),\text{ for } n \geq n_{0} $$ With $c_1,c_2,n_0 > 0$, $\lg(k) = \Theta(\lg(n))$ By deriving the actual relationship of $k$ with ...
1
vote
0answers
38 views

Asymptotic large order approximation for Bessel function expression

How does one find the asymptotic large order approximation for $\sup_{0\le x\le\infty} \left(\sqrt{x} J_n(x)\right)$, where $J_n$ is the Bessel function of the first kind and order $n$. This is NOT a ...
0
votes
0answers
28 views

How to study the asymptotic behavior of $f(r)=\int_0^1 dx\, \text{Li}_2\Big(1-\frac{r}{x(1-x)}\Big)$ for small $r$?

How does one study the asymptotic behavior of the integral $$f(r)=\int_0^1 dx\, \text{Li}_2\Big(1-\frac{r}{x(1-x)}\Big)$$ as $r\rightarrow0$ from positive values? Here $\text{Li}_2$ is the ...
4
votes
1answer
362 views

Can a curve be an asymptote?

$f(x)=x^3+\frac{3}{x-1}$ This was the question given to me.I replied that $f(x)$ will have only a single vertical asymptote of $x=1$. My teacher told that there'll be be two asymptotes.One is the ...
1
vote
2answers
79 views

Laplace's Method (Integration)

Consider the integral \begin{equation} I(x)=\int^{2}_{0} (1+t) \exp\left(x\cos\left(\frac{\pi(t-1)}{2}\right)\right) dt \end{equation} Use Laplace's Method to show that \begin{equation} I(x) \sim ...
0
votes
1answer
27 views

Number of rationals with denominator less than $N$

This is probably a duplicate since it seems like elementary number theory, but didn't find it after a cursory search. Let $r(N)$ be the number of rationals in $[0,1]$ with denominator less than or ...
2
votes
2answers
44 views

Order estimates question and big O notation

How can I show that $y(x) = 1 - \cos(x)$ is $\mathcal{O}(x^2)$ for $|x| <<1$ ? Additionally, with the $|x| << 1$ is there a precise definition? I tried to google it but nothing conclusive ...
0
votes
0answers
34 views

$f(n)=3f(\frac{n}{3})+O(logn)$

I was asked to figure out the time complexity analysis for the following recurrence relation: $f(n)=3f(\frac{n}{3})+O(logn)$ I worked it out as O(nlgn), Would like to know if this is right or ...
1
vote
0answers
18 views

Asymptotic expansion of integrals of the form $\int_{\mathcal{D}} \exp(\lambda\, \phi(x))\, g(x) \,dx$ for small $\lambda.$

In the limit $\lambda\to\infty$ the asymptotic expansion of integrals of the form $\int_{\mathcal{D}}\exp(\lambda\,\phi(x))\,g(x)\,dx$ (where $\mathcal{D}\subseteq \mathbb{R^n}$ denotes the domain of ...
0
votes
2answers
32 views

Big O notation and limits

I'm wanting to take the $\lim_{x\to \infty} \frac {O(1)}{x^s}$, where $O(1)$ is Big O notation and $s>1$. I can see that it will be zero but I'm wanting to do it somewhat rigorously. Can I take the ...
0
votes
1answer
24 views

Show a function similar to $(1/x)lnx$ becomes small as x grows

I am tasked with showing that, for $l \gg k$, $$ t = \frac{1}{l-k}\ln(l/k) $$ is small (it is given that $t$ is positive). Intuitively, this seems correct because it is 'similar' to $$ \frac{1}{x} ...
1
vote
0answers
44 views

Proving $n^{10\log(n)} = O((\log^n(n))$

I need to decide which of the following is correct: $n^{10\log(n)} = O((\log^n(n))$ $n^{10\log(n)} = \Theta((\log^n(n))$ $n^{10\log(n)} = \Omega((\log^n(n))$ So I'm saying $n^{10\log(n)} = ...
0
votes
0answers
12 views

Question about big omega proof

I'm not sure if I should post it here or in StackOverflow, but anyway... Prove that: $n^5-2\log{n}=\Omega{(n^5)}$. Proof: We need to find $c, n_0 \geq0$ such that, for all $n \geq n_0$, ...
4
votes
0answers
60 views

Growth of $n!!\dots !$

The asymptotic growth of the factorial function $n!$ is famously given by Stirling's formula as $$n! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n$$ Is there a similar formula for the iterated ...
0
votes
1answer
27 views

Suppose that $f (x)$ is $O(g(x))$. Does it follow that $2^{f(x)}$ is $O(2^{g(x)})$?

Suppose that $f(x)$ is $O(g(x))$. Does it follow that ? First, I start from for some $c$ is a real number. Then, I find . But, if i start from , I just find . I confused with that different form.
1
vote
1answer
76 views

Expectation and Variance of random walks

Consider random walks of fixed length (e.g. $5$) starting at node $u$ in an undirected and connected graph with $N$ vertices. If a node $k$ has $N_k$ edges, the probability of the walk reaching any of ...
0
votes
0answers
19 views

How to do this asymptotic task?

Let a(n) be the amount of natural numbers, which are smaller than n, and their prime divisors are only 2 and 3. For example: 6 is good, because it only has 2 and 3 has prime divisors, but 10 is not ...
1
vote
1answer
27 views

Suppose that $f (x) =O(g(x))$. Does it follow that $\log |f (x)| =O(log |g(x)|)$?

Suppose that $f(x)=O(g(x))$. Does it follow that $\log |f (x)|=O(log |g(x)|)$? I start from $f(x)=O(g(x))$, until I get Does it mean $\log |f (x)|=O(log |g(x)|)$?
0
votes
0answers
19 views

Non-deterministic multiplication algorithms

Are there any algorithms for non-deterministic Turing machines that can compute the decision problem $mn=x$ (where $m=O(n),x=O(n^2)$) faster than the equivalent deterministic algorithm? Equivalently, ...
0
votes
1answer
37 views

How to solve this recurrence, $T(n) = T(\sqrt{n}) + n$ using recursive tree method?

How to solve this recurrence, $ T(n) = T(\sqrt{n}) + n $ using recursive tree method? I draw the tree and got a sum, $ T(n) = T(1) + ( n + n^{\frac 12} +n^{\frac 14}+n^{\frac 18}+\ldots +1) $ I need ...
2
votes
2answers
31 views

How to prove that $2^{n+1} = \Theta(2^n)$?

I have a problem were I need to prove big theta. $f(n) = 2^{n+1} = Θ(2^n)$. I proved that this was true for big O but I'm not sure how to go about proving big Theta.
1
vote
4answers
48 views

Does the inequality $ n! > A \cdot B^{2n+1}$ hold for sufficiently large $n$?

Suppose $A,B >0$ are given constants. Is it possible to find a large enough $n \in \mathbb{N}$ such that $$ n! > A \cdot B^{2n+1}?$$
1
vote
1answer
141 views

Which is the greatest integer value of $a$, for which $A'$ is asymptotically faster than $A$?

The recurrence relation $T(n)=7T\left( \frac{n}{2}\right)+n^2$ describes the execution time of an algorithm $A$. A "competitor" algorithm, let $A'$, has execution time $T'(n)=aT'\left( \frac{n}{4} ...
3
votes
0answers
33 views

Proof $\mathcal{O}(f(n)) = \mathcal{O}(g(n)) \iff f(n) \in O(g(n)) \land g(n) \in \mathcal{O}(f(n))$

There is an exercise that ask me to prove this logic formula about the complexity of algorithms: $\mathcal{O}(f(n)) = \mathcal{O}(g(n)) \iff f(n) \in O(g(n)) \land g(n) \in \mathcal{O}(f(n))$ ...
0
votes
2answers
19 views

How would I go about proving these.

I need to prove or disprove these two problems, but I'm not sure I did it right. $$(a).\quad f(n) = 2^n+1 = O(2^n)\\ (b).\quad f(n) = 2^n+1 = Θ(2^n) .$$ What I tried for the first one is, ...
6
votes
2answers
117 views

Prove or disapprove the statement: $f(n)=\Theta(f(\frac{n}{2}))$

Prove or disapprove the statement: $$f(n)=\Theta(f(\frac{n}{2}))$$ where $f$ is an asymptotically positive function. I have thought the following: Let $f(n)=\Theta(f(\frac{n}{2}))$.Then $\exists ...
4
votes
1answer
46 views

Upper bound for $\prod_{ 5 \leq p <n} p^{\frac{n}{p-1}}$

Does anyone know how I could get a good upper bound for the following: $$R := \prod_{\substack{ p \; \text{prime} \\ 5 \leq p < n}}p^{\frac{n}{p-1}}$$ I'm not that skilled at asymptotic analysis ...
1
vote
1answer
21 views

Simplifying $f(n)$ by substituting, for $n$, an appropriately chosen function $n(x)$ to observe limiting behaviour of $f(n)$. Is this justified?

Say, I'm comparing two functions $f(n) = (ln(n))^2$ and $ g(n) = n^{0.01}$ as $n \rightarrow \infty$, by evaluating $\lim_{n \rightarrow \infty } \frac{f(n)}{g(n)} = \lim_{n \rightarrow ...
0
votes
0answers
7 views

Comparing Growth Rates

Suppose I want to compare the growth rate of some function $f(x)$ as $x\to a$ and another function $g(x)$ as $x\to b$. How do I go about doing that? For example, I want to decide whether ...
3
votes
1answer
67 views

Estimating an unusual infinite sum

I came across the following summation, which I would like to estimate. I only need an answer which is correct up to a constant multiple; one can assume that $a, b, c$ are real numbers in the range ...
0
votes
1answer
37 views

Name of the difference between an asymptote and the curve that approaches it

Consider a function, say a hyperbola, and its asymptote. Is there a specific term for the difference between the two? Answers specific to hyperbola, as well as answers about general terminology, are ...
0
votes
0answers
21 views

finding the n in Aymptotic notations

consider any quadratic function $f(n) = an^2 + bn + c$, where a, b, and c are constants and $a > 0$. Throwing away the lower-order terms and ignoring the constant yields $f(n)= \theta(n2)$. ...
1
vote
3answers
50 views

Prove line asymptotic to curve

I have a function denoted as: $f(x) = \frac{x}{1+e^\frac{1}{x}}$ I want to prove the line: $g(x)= \frac{x}{2} - \frac{1}{4}$ Is asymptotic (slant asymptote) to the above function when approaching ...
0
votes
3answers
38 views

Asymptotic notation (big Theta)

I'm currently in the process of analyzing runtimes for some given code (Karatsuba-ofman algorithm). I'm wondering if I'm correct in saying that $\Theta(\left\lceil n/2\right\rceil) + \Theta(n)$ is ...
1
vote
1answer
57 views

Big-theta notation

I was wondering about big-theta ($\Theta$) notation. A) Is $\Theta(n/2) \leq \Theta(n)$ for $n$ being an integer? I know that $n/2 = O(n)$, but does it also mean that $\Theta(n/2) \leq \Theta(n)$? ...
2
votes
3answers
40 views

Lower bound for the falling factorial $(2n)_{n}$

I'm looking for a lower bound for the falling factorial $$(2n)_{n}:= \frac{(2n)!}{n!}$$ I saw on Wikipedia that $n! > \sqrt{2{\pi}n}(\frac{n}{e})^n$ . So I assume that a possible lower bound ...
1
vote
1answer
29 views

Dealing with floor function in binomial coefficients

I'm trying to estimate $\binom{n}{\left \lfloor{\alpha n}\right \rfloor }$ asymptotically using Stirling's formula. However, I'm a little lost with what to do about the floor function here. In the ...
1
vote
1answer
34 views

Stuttering Subsequence Problem - Explain the example

I'm reading an article that deals with solving the stuttering subsequence problem in $\Theta (n)$. The article can be found here: http://www.cse.yorku.ca/~andy/pubs/Stutter.pdf Some background on ...
0
votes
3answers
48 views

Why does $\lim_{ t\to 0} \frac{o(t^2)}{t} = 0$?

Why does $\lim_{ t\to 0} \frac{o(t^2)}{t} = 0$? $\sqrt t = o(t^2) \implies \lim_{t\to 0} \frac{\sqrt t}{t} = \infty$ Maybe I don't understand completely the little-o notation.
2
votes
1answer
43 views

I need to show the following two limits

First, for $a>-1$: $$\lim_{n\to\infty}\frac{a+1}{n^{a+1}}\sum_{j=1}^nj^a = 1$$ Second, for $p>0$: $$\lim_{n\to\infty}\frac{e^a-1}{e^{a(n+1)}}\sum_{j=1}^ne^{aj} = 1$$ In particular, why do we ...
1
vote
1answer
16 views

Is Θ(⌈x/4⌉) = Θ(x)?

I'm currently working on aysmptotic notation. I know the basic laws of big theta, O, and omega. But I'm having a little confunsion in understanding simplifying the expressions (if that's even ...