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

learn more… | top users | synonyms (1)

2
votes
0answers
21 views

Asymptotics on the largest prime for which $x^n+1\equiv y^n$ has no nonzero solution

It $\let\epsilon\varepsilon\let\leq\leqslant\let\geq\geqslant$is a well known result that for every $n\in\mathbb N$, $x^n+1\equiv y^n\pmod p$ is non-trivially solvable for sufficiently large primes ...
1
vote
1answer
20 views

Closed form for estimated sum with different asymptotic bounds?

I found asymptotic lower and upper bounds for a summation as follows: $$ 1 - O\left(\frac{\log_2^2 n}{n}\right) \le \sum_n f(n) \le 1 + O\left(\frac{1}{n}\right).$$ If you want to write it in a ...
2
votes
1answer
22 views

Need an Algorithm Such that $\sum_{k-i}^{j}{A[k]}$

I need an algorithm for real application. Suppose we have array A (positive & negative ) numbers. we want to find index i, j such that $\sum_{k-i}^{j}{A[k]}$ has the lowest difference to zero. ...
0
votes
1answer
73 views

What are sets and classes in maths, and how are they related to $O()$ and $o()$ notation?

Are there many definitions of sets and classes in mathematics, as given in Formal definion of the notations used in measuring time complexity? And in particular, why the notation given in Fedja's ...
0
votes
0answers
31 views

Big O evaluations

I'm confused about how to approach Big O problems. I'm presented two functions: $$f(n) = 4^{log_4n}$$ and $$g(n) = 2n +1$$ I simplified f(n) to: $$f(n) = n$$ Now I'm not sure how to compare f(n) ...
2
votes
1answer
40 views

Asymptotic expansion of an integral with exponential decay and highly oscillating kernel [on hold]

I would appreciate if one can get the leading term of the following integral: $$I(x) = \large{\int}_0^\infty \frac{g(s)}{\sqrt{s^2 + \frac 1 4}}e^{- i x s- m x\sqrt{s^2 + \frac 1 4}}ds$$ as ...
0
votes
1answer
42 views

Big-Oh notation proofs [on hold]

a) $f(n) \quad \Omega (g(n))$ b) $f(n) \quad \Theta (g(n))$ c) $f(n) \quad \Theta (g(n))$ d) $f(n) \quad \Theta (g(n))$ Am not sure why I got lots of $\Theta (g(n))$ , am I correct in the ...
1
vote
1answer
22 views

Do small o, small omega, and big theta cover all relationships between two functions

Given any two functions $f(n)$ and $g(n)$ is one of these three statements always true: $f(n) \in o(g(n))$ $f(n) \in \omega(g(n))$ $f(n) \in \Theta(g(n))$ Logically, this makes sense to me. For a ...
1
vote
1answer
21 views

Omega Notation and Average Running Time Problem

if we have an algorithm that average running time of randomized algorithm A for input of size n is equal to $\theta(n^2)$. why there would be an input data such that A solve it in $\Omega(n^{3n})$?
0
votes
1answer
19 views

How do you solve a recurrence with a functin through induction?

I found the answer in part-A by substitution, as O(n) from; T(n/2^k) = T(1).... n/2^k = 1..... so k = 1og2(n)..... T(log2(n)) = T(n/n)+5.... so O(n) IS THE ANSWER, Correct me if am wrong because am ...
3
votes
1answer
51 views

Details from a Proof that a Tournament has Property $S_k$

(Edit: While the context is not central to my question, I decided to include it anyway to make the question a little more searchable.) Some technical details are omitted from a theorem in Alon and ...
0
votes
0answers
30 views

Taylor series expansion and Laplace transform final value theorem

I cant figure out how some transformations are made in one article on physics. Here is expression in s-domain and they want to find its asymptotic value. $$ \xi(s) = \nu_1(s+1)=\frac{1}{(s+1)} ...
-2
votes
0answers
55 views

$O$, $\Omega$, or $\Theta$ functions of f(n) and g(n)? [on hold]

I am new to this topic, but I managed to try some problems. I am not sure of my answers, so I want to be checked here before I hand in; a) $f(n) \quad \Omega (g(n))$ b) $f(n) \quad \Theta (g(n))$ ...
0
votes
1answer
35 views

Confusion with Big-oh

So, big-oh means: for at least one choice of a constant k > 0, you can find a constant a such that the inequality f(x) < k g(x) holds for all x > a So let's evaluate the statement $1 = ...
2
votes
0answers
43 views

Density of Pythagorean triples

We define a Pythagorean triple as a triple $<a,b,c>$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$. In order to avoid duplicates, we say that a triple $<a,b,c>$ is legit iff $b>a$. ...
4
votes
0answers
34 views

Boundary Layer, leading order, Pertubation Theory, Differential Equations

I have got the following problem, taken from Multiple Scale and singular perturbation methods, Kevorkian & Cole book, page 94, exercise 1.b.: Find the leading order of the problem: $\varepsilon ...
1
vote
3answers
41 views

Big-O, Omega, Theta and Orders of common functions

Based on this table, is it generally going to be true that for two functions whose most "significant" terms are of the same order that they will be big-Theta each other? And a function of order ...
1
vote
0answers
47 views

Find a closed form for the constant term

In a previous question, an asymptotic expansion was provided for the weighted divisor summatory function $\displaystyle \frac {d(n)}{n}$: $$\sum_{n\leq ...
1
vote
0answers
56 views

Is 1/x the “slowest” asymptotically falling off differentiable function?

As a physicist, I tend to think about $\sim 1/x$ as the "slowest" fall-off of a "reasonable" function. Let us state this formally: $${\rm lim}_{x \to \infty} f(x) = 0, f(x) \in Reas \implies \exists A ...
0
votes
0answers
14 views

Showing that $\prod_i{\frac{qi-1}{qi}}=\exp(-\frac{\log n- \log q +O(1)}{q})$

I'm currently making my way through Dixon's paper 'The Probability of Generating the Symmetric Group'. (It can be found here.) In the proof of lemma 3 it is asserted that ...
1
vote
1answer
34 views

Proving that $ \frac{1}{n}\int_{-\infty}^{\sqrt{n}w}k(v/\sqrt{n})\phi(v)dv$ is $O(n^{-1})$

Suppose that $h:\mathbb{R}\to\mathbb{R}$ is infinitely differentiable. Define \begin{equation} k(w)=\left\{ \begin{array}{ll} \frac{d}{dw}\left(\frac{h(w)-h(0)}{w}\right)&w\neq 0,\\ ...
1
vote
1answer
36 views

Switching Limits and summation

I'm currently working on proving some theorems and there is one recurring problem that I somehow can't solve. $a_n$ is a real sequence in either $[0,1]$ or $\mathbb{R}$ that approaches $0$. ...
1
vote
1answer
48 views

How to rigorously simplify an expression with Big-Oh Composed within another Big-Oh.

I am trying to show the following: $$ O(e^{n(\cos n^{-2/5}-1)}) = O(e^{-Cn^{1/5}})$$ The problem I'm having is I'm trying to get a hang of asymptotic notation, and I can't quite figure out how to ...
1
vote
1answer
31 views

Asymptotics of logarithm: $\frac{1}{n}\ln(a+o(1)) = \frac{1}{n}\ln(a)+o(\frac{1}{n})$

I am having problems with the use of the little oh notation my professor is adopting in the solutions to some exercises. As an example I do not understand why $$ \frac{1}{n}\ln(a+o(1)) = ...
1
vote
1answer
30 views

Lower bound on $F$ under the assumption $\theta F(s)\le sF'(s)$

Let $F(s)=\displaystyle \int_0^{s}f(t)\,\mathrm dt$. We suppose that there exists $\theta>2$ such that $\theta F(s)\le f(s)s$ for all $s\in \mathbb{R}$ and that $F(s)>0$ for all ...
0
votes
1answer
19 views

What's time complexity of algorithm for “Word Break”?

Word Break(Dynamic Programming) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible ...
1
vote
0answers
32 views

Asymptotic behaviour / Convergence

Let $0<\omega<\infty, \mu >0$ and $z \in \mathbb{R}.$ In my book, it is written that we have the following asymptotic behaviour: i) Claim: $$\lim_{t \rightarrow \infty} \frac{z ...
1
vote
1answer
54 views

Can I prove this, or hopeless? Deviating too much from mean

Can I prove this: We have a sequence of vectors $\left(X_i(n)\right)$ for $i=1,\ldots,t$, where $n\rightarrow \infty$. $t$ does depend on $n$ and is Chosen such that $1 \ll t \ll n$, for instance, ...
0
votes
0answers
14 views

Simplification of a polynomial before Asymptotic series expansion

I am wondering about a very basic point related to "Asymptotic series expansions". There is a function $f(R)$ which must be expanded as $R$ goes to $ \infty $. Consider that $f(R)=g(R)*p(R)$ where ...
0
votes
1answer
21 views

Show that $\int_{2}^x\frac{\pi(t)}{t(t-1)}dt=\log \log x+ O(1)$

Show that $\int_{2}^x\frac{\pi(t)}{t(t-1)}dt=\log \log x+ O(1)$ Do you use the fact that $\pi(t) = \frac{t}{\log t} + O\left(\frac{t}{\log^2t}\right)$ and then $\int_{2}^x\frac{\pi(t)}{t(t-1)}dt= ...
0
votes
1answer
35 views

How would you show $\pi(x)\log(1-\frac{1}{x}) \sim \frac{1}{\log x}$

How would you show $\pi(x)\log(1-\frac{1}{x}) \sim \frac{1}{\log x}$? Would you use $\lim_{x\to \infty}\frac{\pi(x)\log(1-\frac{1}{x})}{\frac{1}{\log x}} = 1$? and how would you show this? Can you ...
1
vote
0answers
23 views

How to show an aymptotic expansion is uniformly valid?

I have an equation $$ nt = u - \epsilon \sin(u) $$ which asks for the first four terms in the asymptotic solution. Hence if the solution is $u_0 + \epsilon u_1 + \cdots.$, expand $\sin(u)$ around ...
0
votes
0answers
19 views

Approximate $_2F_1(a,b;c;x)$ for large (maybe negative) values of $a, b, c$?

I need asymptotic approximations of the Hypergeometric function $_2F_1(a,b;c;x)$ for large positive values of $a, b, c$. Specifically, I need approximations for all the possible regimes, in which one ...
2
votes
0answers
18 views

Incomplete Beta function $\text{B}_x(\alpha,\beta)$ approximation for large $\alpha,\beta$?

I need good asymptotic approximations to the incomplete Beta function $\text{B}_x(\alpha,\beta)$ for large values of $\alpha,\beta$. Specifically, I need approximations valid for the following ...
0
votes
1answer
27 views

For which function $f$ is $1 \ll \sum_{i=1}^{n} i \cdot i^{-f(n)} \ll n$?

I am interested in the expected value of a power-law Distribution. I would like to let the Parameter $f(n)$ depend on $n$ for $n \rightarrow \infty$. And now I would like to determine $f(n)$ such ...
-1
votes
1answer
35 views

How do I prove that $a = n/2$ is a tight upper bound for the recurrence relation $T(n) = T(n-a) + T(a) + n$?

I have a recurrence relation: $$T(n) = T(n-a) + T(a) + n$$ which happens to be $O(n^2)$ complexity. How do I now prove that: $$a = n/2$$ is a tight upper bound for this relation? I have been ...
1
vote
1answer
36 views

Closed-form term for this expression

I have a normal Distribution $X \sim N(\mu, \sigma)$. Is there an easy way to give an asymptotic estimate with small error (I would prefer with relative error $\rightarrow 0$) for $P[X \geq k]$? We ...
0
votes
2answers
38 views

How to prove that $n^{1.1} \not\in O(n(\log n)^2)$

This is a problem from a university exam: True or false: $n^{1.1} \in O(n(\log n)^2)$. The solution says False, but I'm unable to prove it. I tried using the limit test for Big-O: $\lim_{n \to ...
2
votes
1answer
26 views

$f(t) = \cos t^{-1} + \int_t^\infty \frac{1}{\tau^2 + f(\tau)^2} d\tau$ implies the integral is $O(\frac{1}{t})$

The following is a quote from "asymptotic methods in analysis" by de Bruijn (p. 136). If we know that the real function $f(t)$ satisfies the relation $$f(t) = \cos t^{-1} + \int_t^\infty ...
2
votes
1answer
32 views

Difference between $\lim P[…]$ and $P[ \lim ]$

In a Galton-Watson branching process the extinction probability is sometimes given by $$\lim_{t \rightarrow \infty} P[X(t)=0]$$ and sometimes as $$ P[\lim_{t \rightarrow \infty}X(t)=0]$$ Is there a ...
2
votes
0answers
76 views

asymptotic expansion of the integral for large tau

How can I proceed to resolve this integral? $$ c_1\int_{-\infty}^{\infty}{\frac{\cos\left(x\tau\right)}{\left(1 + c_{2}\,x\right)^{\alpha}}}\, \,{\rm d}x $$ where $c_1, c_2$ are positive constants, ...
2
votes
2answers
71 views

Growth Rate of Alternating Sign Matrices

I am trying to compute the best growth rate for the following sequence $$ a_n=\prod_{k=0}^{n-1}\frac{(3k+1)!}{(n+k)!} $$ This sequence counts the number of $n\times n$ alternating sign matrices: ...
0
votes
0answers
22 views

Change of Variables in an Asymptotic Big-Oh Situation

I'm looking at the function $cos(x)^n$ as $n$ varies. It appears to be gaussian. The book says it's easy to verify that it is Gaussian: set $x=\omega/\sqrt n$, and then a local expansion yields: ...
0
votes
2answers
36 views

Asymptotic behaviour of $\prod_{p \leq x} (1 + 4/(3p) + C p^{-3/2})$

I'm reading Montgomery and Vaughan and in it they state quite simply \begin{equation} \prod_{p \leq x} \left(1 + \frac{4}{3p} + \frac{C}{p^{3/2}} \right) \ll (\log x)^{4/3} \end{equation} as $x ...
6
votes
1answer
33 views

Equivalent of a sequence in regard to a certain length of a cycle for $\mathfrak{S}_{n}$

Let $n \in \Bbb{N}$ ( for me $0\notin \Bbb{N})$. Find the limit as $n$ tends to $+ \infty$ of the following sequence $$\frac{\alpha_{n}}{n}$$ where $\alpha_{n}$ is the number of permutations of ...
8
votes
0answers
142 views
+100

How to estimate $Pr[vr_i=ur_i]$ in the presence of rotations

Suppose we want to compute the probability that for two different random vectors (with elements that are $0$ or $1$), denoted by $v$ and $u$, multiplying them with the rotations of a random vector $r$ ...
1
vote
2answers
35 views

Differential Equations: Asymptotic Behavior

I'm new to differential equations, so any help will be grateful. I've been looking at this problem: Examine the slope field of the following differential equation. Based on the direction field, ...
0
votes
1answer
33 views

Inequality with little-o notation

I'm having trouble justifying the following: For large $n$, \begin{align*} -\log f(n) & < \log n + o(\log n)\\ \implies f(n) &> n^{-1} \log^3(n) \log(10) \end{align*} I think basically ...
3
votes
1answer
72 views

Divisor function asymptotics

Define $\tau_{r}(n) = \sum_{d_1...d_r = n}1$. One exercise in a book on sieve theory asked for an elementary proof by induction of the fact that $$\sum_{n\le x}\tau_r(n) = \frac{1}{(r - 1)!}x(\ln ...
0
votes
1answer
61 views

Is this possible or hopeless to try to prove?

If I have $x_1, ..., x_k=o(n)$ and $j=O(1)$. Is it possible to prove something like: $$\sum_{i=1}^k {n \choose j} \left(\frac{x_i}{n}\right)^j \left(1-\frac{x_i}{n}\right)^{k-j} \sim {n \choose j} ...