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
1answer
36 views

What is the asymptotic behavior of this integral?

The function $F(x)$ is defined by the following integral $$F(x)=\int_0^x\frac{\left(1-y^3\right)^a}{\sqrt{\left(\dfrac{1-y^3}{1-x^3}\right)^b-\left(\dfrac{y}{x}\right)^4}}\,dy$$ where $a$ and $b$ ...
2
votes
0answers
16 views

Find Theta Class of T(n) = T(3n/4) + T(n/6) +5n [duplicate]

I'm not quite sure I can apply the Master Theorem to T(n) = T(3n/4) + T(n/6) + 5n. It is not in the normal form of T(n) = aT(n/b) + f(n). Is it possible to apply the MT to it? If not, can the ...
1
vote
1answer
67 views

A sum of Stirling numbers of the second kind

Find a formula (either exact or asymptotic in $N$) for $S(N)$, where \begin{equation} S(N) = \sum_{n=N}^\infty \sum_{k=N}^n \sum_{j=0}^k \binom{k}{j} (-1)^{k-j} (1+j)^n \frac{t^n}{n!}. \end{equation} ...
0
votes
0answers
34 views

Find the best Big-O estimate

Find the best (i.e., lowest) big-O estimate for the following function: $f(n) = 1 + 3 + 5 + 7 + ...+ (2n-1)$ Since the sum would be $f(n)= \frac{1 + n(2n-1)}2$, that would leave $\frac {2n^2 -n ...
15
votes
3answers
543 views

Can a function “grow too fast” to be real analytic?

Does there exist a continuous function $\: f : \mathbf{R} \to \mathbf{R} \:$ such that for all real analytic functions $\: g : \mathbf{R} \to \mathbf{R} \:$, for all real numbers $x$, there exists ...
0
votes
1answer
152 views

asymptotic sequence

I am asked to prove that $x^n(a+\cos(x^{-n})$ is an asymptotic sequence for $n=0,1,2,...$, $a>1$, $x\rightarrow 0$ but its derivative wrt x isn't an asymptotic sequence. ...
0
votes
3answers
53 views

Is $n^\frac{1}{10} \in O((\log n)^{10})$?

This question came up in a recent discussion: is $n^\frac{1}{10} \in O((\log n)^{10})$? First time I've come across a power of a log in a long time, and as far as I recall, there are no identities ...
1
vote
1answer
42 views

$N$ is approximately linear in $d$ for $N^d=\frac12 e^{N}$

let us look at the function $N^d e^{-N}$, for each $d\in \mathbb{N}$. The graphs of the function for various values of $d$ show a striking phenomenon: the graph look parallel, and with a near-constant ...
0
votes
1answer
23 views

Big O Notation asymptotic relationship

I cannot prove correctness/incorrectness of the implication of two functions f(n) and g(n) in Big-Oh/asymptotic notation $$g(n) = \Omega(f(n)) ) \implies g(n) = O(n^2f(n))$$ I believe $g(n) = ...
0
votes
0answers
13 views

Renormalization Group

I am studying singular perturbation technique right now. Can anyone suggest introductory books on singular perturbation using renormalization group method? I have several books on perturbation theory ...
1
vote
1answer
39 views

Why does $\frac{\frac12 x+\frac18x^2+O(x^3)}{\frac12x-\frac18x^2+O(x^3)}=1+\frac12x+O(x^2)$?

I was reading the solution to a limit through Taylor expansion but did not understand this passage: $$g(x)=\frac{1-\sqrt{1-x}}{\sqrt{1+x}-1}=\frac{\frac12 ...
1
vote
4answers
56 views

How to check if $n!$ is $ O(2^n)$

How can I check if $n! \in O(2^n)$? The definition of $f$ being $O(g)$ is $f(n) \le c g (n)$, where $c>0$. So it would mean $n! \le c 2^n$. What is the clearest way to solve this? (As I am ...
1
vote
1answer
24 views

For what maximum positive $k$ is $2n \sin^{2} \frac{\pi}{n} > \tan \frac{k\pi}{n}$ true?

I am trying to find the maximum value of $k$ such that the inequality $$2n \sin^{2} \frac{\pi}{n} > \tan \frac{k\pi}{n}$$ is satisfied. I impose restrictions that $n \in \mathbb{Z}$ with $n \geq ...
4
votes
1answer
77 views

Does “the functions agree at infinity” mean anything?

I want a way to describe how two continuous functions $f,g \colon (X-x) \to Y$ might "share a limit" at the point $x$ when unfortunately neither of $\displaystyle \lim _{y \to x}f(x)$ or ...
0
votes
1answer
28 views

Average of numbers converges, then what happens to the maximum

Let $\{a_n\}$ be a positive sequence of numbers such that $\displaystyle \frac1n\sum_{i=1}^n a_i \to a$ where $a>0$. Then can we say anything about the order of $\displaystyle b_n=\max_{i\in n} ...
4
votes
3answers
71 views

Extracting the divergent part of an integral

I want to evaluate the integral $$ \int_0^1 \frac{2x(x-2)(1-x)}{(1-x)^2 + ax} \, \mathrm{d}x$$ in the limit of small $a$. For $a = 0$ this integral is divergent due to the $1/(1-x)$ pole. The exact ...
0
votes
0answers
39 views

10-Subset Sum: Given a set of integers K and an integer M, is there a subset of exactly 10 elements of K whose sum equals M?

I understand that the more general Subset Sum problem is NP-complete, but I am under the assumption that this more specific version of the problem can be solved in polynomial time. However, I can't ...
0
votes
2answers
71 views

Approximation of a quotient that involves the Lambert function.

I would like to find an asymptotic upper bound for $$\frac{-\ln n}{W(- \ln^{-c}n)}$$ where $c$ is positive and $W$ is the Lambert function. More precisely, I want something which dominates this ...
5
votes
0answers
34 views

More elegant derivation of the shift in median bin occupancy

In answering Median of a multinomial variable, I found to my own surprise through a somewhat tedious calculation that the expected value of the median of the ball counts in $3$ bins into which $n$ ...
0
votes
1answer
33 views

Function $(2.2)^n$ — what is it?

The running time of an algorithms is $(2.2)^n$. I have to tell what is the maximum $n$ for reaching 1.000.000 steps. What type of a function is $(2.2)^n$? How its output depends on the input $n$? ...
2
votes
1answer
56 views

Asymptotic behavior of integrals of Legendre polynomials

By definition $\int_{-1}^1 |P_n(x)|^2 dx = O(n^{-1})$. What about the other powers? Do we know how $\int_{-1}^1 |P_n(x)|^k dx$ behaves for any $k$? Maybe $O(n^{-k/2})$?
0
votes
0answers
31 views

I am looking a comparison of this computation and Riemann's approach for $lcm(1,2\ldots,x)$

Looking a comparison with a reasoning due to Riemann, I ask to me about the behaviour as $x\to\infty$ of the following arithmetical function $$ \left( \prod_{n\leq x}n^{-\mu(n)}\right)\cdot \left( ...
1
vote
1answer
30 views

Asymptotic notation: What does $o(\epsilon_\text{mach})$ mean?

I'm having serious problems to understand what people mean when they write $o(\epsilon_\text{mach})$, where $\epsilon_\text{mach}$ stands for the machine epsilon. I'm seeing this in backward analysis ...
1
vote
0answers
14 views

Is $O(x^2)$ equal to OR a tighter bound for $O(x(x-y))$ if $x, y >0$ and $x>y$ alway hold?

In the question, $O$ is the Big-O notation, please see https://en.wikipedia.org/wiki/Big_O_notation. $x$ and $y$ are variables. Here, let me give you an example showing there exist such questions in ...
0
votes
1answer
44 views

Finding family of curve for given asymptotes

I need to find possible curves, with asymptotes given as $x=0 (x \to -\infty)$ and $y=mx \hspace{0.5cm} m>0$. it is easy to find curves for individual lines, $y= \exp(-\lambda_1 x) + mx$ for $y=mx$ ...
0
votes
2answers
37 views

Big O for a $\cos$ series

I have to show that $ \sum_1^N \cos(nx) = O(\frac 1{|x|}), [-\pi, \pi] $, x different from 0. I really don't know how to show that. I obviously know that $\cos(nx)$ is bounded by $1$, I know what ...
1
vote
0answers
32 views

Products of $k^{\mu(k)}$, where $\mu(n)$ is Möbius function, and the Prime Number Theorem

We can write $$e^{-\Lambda(n)}=\prod_{d\mid n}d^{\mu(d)},$$ where $\mu(n)$ is the Möbius function and thus $\Lambda(n)$ is von Mangoldt's function. Then taking the product from $1$ to $N$ we've for ...
0
votes
1answer
18 views

Simple Sigmoid function that levels off at specific points

I need to construct a simple Sigmoid function that levels off at specific values of x, as in this curve: What is the most simple Sigmoid function that I can use ...
-2
votes
5answers
97 views

Hello. I need to show that $\sqrt n$ grows faster than $(\log n)^{100}$ [closed]

Is there an easy way to show that $$\lim_{n\to \infty}\frac {(\log n)^{100}}{\sqrt n}=0 $$
5
votes
2answers
71 views

How is it posible that $f + g \in O(f)$?

I am confused how to do this question. Intuitively it doesn't even make sense how a function $f$ plus another function is in $O(f)$. How can I approach this question: $$ n\log(n^7)+n^{\frac{7}{2}} ...
0
votes
1answer
45 views

Determine numerical infinity for Schrodinger equation $−\psi''(z) − (iz)^ N \psi(z) = E\psi(z)$

Consider the following one dimensional Schrodinger equation within the complex plane of $z$ $$ −ψ''(z) − (iz)^ N ψ(z) = Eψ(z). $$ where $N$ can be any real number, the boundary condition is $ψ(z) → 0$ ...
0
votes
1answer
13 views

Which one is asymptotically larger?

The question is to find out which among $n^\sqrt{n}$ or $n^(log_2 n)$ is asymptotically larger? Now as a solution I read somewhere that if we take log on both sides and then compute which one is ...
3
votes
2answers
89 views

Prove that the value of the constant $C$ must be $1$

After proving the prime number theorem in class, our professor directs us to a remark by Lagrange that for large values of $x$, $\pi(x)$ is approximately equal to $$ \frac{x}{\log x - B}. $$ (This is ...
0
votes
0answers
17 views

Asymptotic growth of $T(n) =T(n/3) + T(n/6) + n ^ \sqrt{\log_2n}$

Can you give a solution or a hint for finding asymptotic bound for following recurrence relation: $T(n) =T(n/3) + T(n/6) + n ^ \sqrt{\log_2n}$ I know from the source of the problem that it is ...
1
vote
2answers
46 views

If for some $n\in\mathbb{N}$, $\lim\limits_{x\to\infty}\frac{f(x)}{x^n}$ exists, then $f$ is rational

I don't know if this statement is true. Let $F$ be a function and suppose $n>0$, $n\in\mathbb{N}$ is the greatest such that there exists $L\mathbf{\neq 0}$ such that ...
2
votes
0answers
34 views

Asymptotic distribution of zero-drift Geometric Brownian Motion as $t \to \infty$

If we fix the drift at $\mu = 0$, then my geometric brownian motion will have stationary mean, but it seems that the variance will grow without bound. What does the limiting distribution look like for ...
0
votes
0answers
7 views

Rate of expected value of $\mathcal{O}_p$

This is certainly very basic but what is the rate of the expected value of a random variable that is bounded in probability. For example, let $X_n = \mathcal{O}_p (a_n)$ is it true that $\mathbb{E} ...
0
votes
1answer
63 views

Prove that $n! = O(n^n)$

I thought $n^n$ was greater than $n!$. How would I go about proving this? I have this so far: Assume that $P$($n$) is true $n!$ = O($n^n$) Assume that $P$($n+1$) is also true $(n+1)! ...
0
votes
1answer
14 views

The Big O Notation and the Thetha Notation

I was instructed to find whether $$x*⌈x⌉*⌊x⌋$$ is$$ O(x^3) $$ or $$Big Thetha(x^3)$$ I tried to do a solution by cases, and i got : if x is not an integer, $$x=b+є$$ $$⌈x⌉=b+1$$ $$⌊x⌋=b$$ Then ...
3
votes
1answer
39 views

Which singular perturbation method should be used for this system?

Consider the system $$ \varepsilon \dfrac{dx}{dt} = -(x^3 - ax + b)$$ $$ \dfrac{db}{dt} = x - x_a$$ where $\varepsilon \ll 1$. Applying regular perturbation methods isn't suitable because when ...
0
votes
0answers
19 views

Linear combination of asymptotic series

I need to compute an expression of the form \begin{equation}J=\sum_{k=0}^N a_k F_k(z)\end{equation} where z is a large parameter, and a_k are easily computable (k and z-dependent) coefficients. I ...
8
votes
0answers
100 views

If $n={k^2 \choose k}$, then what is $k$?

Given that: $$n={k^2 \choose k}$$ what is $k$ as a function of $n$? So far, I have found the following approximation: $$ n \approx (k^2)^k = (k^k)^2 $$ $$ \sqrt{n} \approx k^k $$ If we take this ...
3
votes
2answers
337 views

Determining the number of levels in a binary tree via algorithm

I am trying to create a divide-and-conquer algorithm for computing the number of levels in a binary tree. In particular, the algorithm should return 0 and 1 for the empty and single-node trees, ...
-1
votes
1answer
22 views

Big O notaion O(n) and logaritms [closed]

Can someone explain me the subjects Big O notation and logarithms please? I can't understand those subjects For example if I have a question like this: recall that logan is the power to which you ...
1
vote
0answers
22 views

Finding asymptotycs of partition function

I have been stuck in this problem and have no idea of how to solve it. I have a hint from the book but don't really see how to use it. Any suggestion or hint would be really appreciated. Thanks! ...
3
votes
1answer
47 views

Verifying a step in the prime number theorem

This is an excerpt from Shapiro, "Introduction to the theory of numbers": Suppose that we have an estimate of the form $$|R(x)|\le \alpha x$$ valid for all sufficiently large $x$ (say $x\ge x_2$). ...
1
vote
1answer
57 views

Time Complexity of Sorting Algorithm

Here's my question: Analyze the runtime of the following algorithm. Will it successfully sort array S of n elements with values from 0 to m-1? ...
0
votes
0answers
21 views

Asymptotic upper bound for recurrence relations

The question is to find asymptotic upper bound for recurrence: (1) $T(n)=(T(n/2))^2$ and (2) $T(n)=(T(\sqrt{n}))^2$ with $T(n) = \text{n for n} \leq 2$ I think I will be able to find the ...
0
votes
1answer
31 views

Asymptotic upper bound $T(n)=(T(n−1))^2$

The question is to find asymptotic upper bound for recurrence: $T(n)=(T(n−1))^2$ $T(n) = \text{n for n} \leq 2$ My attempt: I've tried to use substitution method and getting: ...
0
votes
0answers
19 views

Big O notation question (conceptual)

In my class, we have defined that $$ f(x) \ll g(x) $$ on $A$ if there exist a strictly positive c such that $$ |f(x)| \le cg(x) $$ for every $x$ on $A$. I'm a bit confused. Say that $ f(x) = x$ ...