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

learn more… | top users | synonyms (1)

0
votes
0answers
14 views

Exponential Averaging Asymptotic Inequality

Let $\lambda_1(t)$ and $\lambda_2(t)$ be nonnegative integrable functions on $[0,\infty)$. Consider the averaging function of $\lambda_1$ $$k(t) = \frac{\int_0^t \lambda_1 e^{-\int_0^s ...
1
vote
1answer
26 views

Calculate limit $\lim_{n\rightarrow\infty}\dfrac{(4n-100)^{4n-100}n^n}{(3n)^{3n}(2n)^{2n}}?$

The limit $$\lim_{n\rightarrow\infty}\dfrac{(4n)^{4n}n^n}{(3n)^{3n}(2n)^{2n}}$$ can be calculated as ...
1
vote
2answers
47 views

Does $\sum\limits_{k=1}^n a_k^2$ imply $\sum\limits_{l=1}^k a_k \in o(\sqrt{n})$?

I'm trying to determine some limits and it makes me wonder if my intuition about asymptotics is just wrong: Our calculus professor used to say that $\sum\limits_{n=1}^{\infty} \frac{1}{n}$ is ...
2
votes
3answers
45 views

Asymptotic behavior of $\sum\limits_{k=1}^n \frac{1}{k^{\alpha}}$ for $\alpha > \frac{1}{2}$

As the title states, I'm interested in the asymptotic behavior of $$\sum\limits_{k=1}^n \frac{1}{k^{\alpha}} , \alpha > \frac{1}{2}$$ for $n \to \infty $. Any hints/ideas?
1
vote
1answer
32 views

Landau Big O, Little o notation, complex example

I stumbled upon a set cardinality asymptotics: $$O(n^{o(1)}),$$ I have a problem interpreting it. Can somebody give me a hint how to look at it?
1
vote
0answers
30 views

What does “combining the solutions in O(n) time” mean?

Algorithm $X$ proceeds by recursively solving $5$ subproblems of one-half the size, then combining the solutions in $O(n\log n)$ time. Algorithm $Y$ makes $9$ recursively calls on ...
0
votes
1answer
33 views

How to quickly determine running time of such recurrence relations?

$$T(n)=5T(\frac{n}{2})+n\log n$$ $$T(n)=9T(\frac{n}{3})+n^2$$ $$T(n)=2T(\frac{2n}{3})+n^{1.5}$$ What are the running times of each $T(n)$? Each one looks like the form of the Master Theorem, but only ...
0
votes
2answers
27 views

Solve the recurrence $T(n)=3T(n/3)+\log n$, $T(1)=1$

So $T(n)=3T(n/3)+\log n$ and $T(1)=1$. I tried to solve this by expanding it out to see a pattern, but I don't really see the pattern: $T(n/3) = 3T(n/9)+\log (n/3)$ $T(n) = 3[3T(n/9)+\log ...
3
votes
1answer
79 views
+50

If $f(x) = \sum \limits_{n=0}^{\infty} \frac{x^n}{2^{n(n-1)/2} n!}$ then $f^{-1}(f(x)-f(x-1))-\frac{x}{2}$ is bounded

For every $x>0$, let $$f(x) = \sum \limits_{n=0}^{\infty} \dfrac{x^n}{2^{n(n-1)/2} n!}.$$ Let $f^{-1}$ be the functional inverse of $f$. How to show there exists a positive real constant $C$ such ...
1
vote
0answers
22 views

Help with understanding how to sketch a graph of y=1/f(x) and y = xf(x)

I'm having problems trying to figure out how to sketch a graph for these 2 questions. Could someone provide me a step by step guide on how to do this? Thanks in advance.
0
votes
2answers
21 views

Is there a mistake in this page on asymptotic expansions?

I think there is an error in section 4.3 of this page - http://aofa.cs.princeton.edu/40asymptotic/ The author says that by taking $x = -\frac{1}{N}$ in the geometric series $\frac{1}{1-x} = 1 + x + ...
0
votes
1answer
28 views

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$?

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$? I do not think it applies because there no $n$ term and there is no $n^k$ for a $k$ which would equal $0$.
0
votes
1answer
26 views

Partial sums of powers of the divisor function

It is easy to establish that $$\sum_{n\le x}\tau(n) \sim n\log n$$ How would one find good bounds on $$\sum_{n\le x} \tau(n)^k $$ for some $k > 0$
1
vote
2answers
34 views

$\lim\limits_{t\to\infty}t-x(t)=0\ ?$

Let $\displaystyle\cases{ x'=\frac{t-x}{1+t^2+x^2} & \cr x(1)=1 }$ be the Initial value problem, prove or disprove $\lim\limits_{t\to\infty}t-x(t)=0$ We've already proved that: for $t>1, ...
0
votes
1answer
29 views

Asymptotic equivalence and $\lim_{x\to 0} \frac{\sin x}{x}=1$

I know that for $x\sim0$ $\sin x$ can be approximated by $x$, hence they are 'asymptotic equivalent in the neighborhood of $x=0$'. According to the definition of asymptotic equivalence, two ...
0
votes
1answer
5 views

If some function f is in big O(some function g), do f and g necessarily need to have the same domain and codomain?

Say I have a function, $g:\mathbb{R} \mapsto \mathbb{R}$. Then would the set $O(g)$ be defined (as explicitly as possible) as: $$O(g) = \{ f:\mathbb{R} \mapsto \mathbb{R} \space|\space \exists C \in ...
0
votes
2answers
40 views

Simple equivalent of the rest of the series $\sum\limits_n\frac1{n^3}$

Consider the converging series \begin{equation} \sum_{n\geqslant1}{\frac{1}{n^3}} \end{equation} I want to find an equivalent of the rest : \begin{equation} R_n=\sum_{k=n+1}^{\infty}{\frac{1}{k^3}} ...
1
vote
1answer
35 views

Applying the master theorem

State the asymptotic runtime found by the master theorem. If the master theorem does not apply state why: 1) $T(n) = $T($n/3)$ 2) $T(n)= $ $5T$($2n/5$) + $n$ 3) $T(n) = 4T(n/2) +15n^3 + 4n^2 +n+4$ ...
0
votes
1answer
21 views

Asymptotic bounds for the solutions of 3d wave equation

Let $u$ solve the 3-d wave equation: $u_{tt}-\Delta u =0$ such that $u=g$ and $u_t=h$ for $t=0$ and where $g$ and $h$ are both assumed to be compactly supported and smooth. I have shown that there ...
1
vote
1answer
89 views

A limit with $((n-1)!)^{1/(n-1)}$ and other roots of factorials

How to prove that the following limit is positive? $$ \lim_{n \to \infty}\left(((n-1)!)^{1/(n-1)}-2\left(\frac{((n-1)!)^3}{(2n-2)!}\right)^{1/(n-1)}\right) >0,$$ where $ n\in \mathbb Z, n>1 ...
0
votes
1answer
17 views

Why does $f(x) \asymp g(x) \implies log(f(x)) = log(g(x)) + O(1)$?

Why does $f(x) \asymp g(x) \implies log(f(x)) = log(g(x)) + O(1)$? Has it got something to do with the fact that \begin{align} f(x) \asymp g(x) \implies \exists c_1,c_2, \text{ such that}\\ ...
2
votes
0answers
47 views

Finding the critical values of a response curve

I have the motion of a forced spring: $$x'' + \kappa x' + x - x^3 = \varGamma \cos(\omega t) \ \ \cdots \ \ (1)$$ and I am investigating the stability of its solutions with forcing period $T = ...
0
votes
1answer
12 views

Show that $\frac{1}{e^\gamma \text{log }x + O(1)} = \frac{1}{e^\gamma\text{log }x} + O\left(\frac{1}{(\text{log }x)^2}\right)$

Show that $\frac{1}{e^\gamma \text{log }x + O(1)} = \frac{1}{e^\gamma\text{log }x} + O\left(\frac{1}{(\text{log }x)^2}\right)$ I'm using one of Merten's estimates in a proof, the one that states ...
1
vote
1answer
24 views

Large $t$ asymptotics of $\int_0^{\infty}\exp(-tx)\exp(-\frac{1}{x^2})dx$

How do I find the asymptotic behavior of $$\int_0^{\infty}\exp(-tx)\exp\left(-\frac{1}{x^2}\right)dx$$ as $t\to\infty$? The Laplace method apparently doesn't work since $\exp(-\frac{1}{x^2})$ isn't ...
0
votes
1answer
32 views

Meaning of the $\{1 + o(1)\}$

Being a software developer, I have the basic understanding of big-O and small-o notation. But currently I've faced set of mathematical problems, where they operate with asymptotics on much more ...
-2
votes
2answers
69 views

If$\ f(n)-g(n)$ tends to a rational number as$\ n \to \infty$, might we say that either both have an “irrational growth” or a “rational” one? [closed]

Let me explain myself.$\ x-y=\frac{a}{b}$ if and only if either$\ x$ and$\ y$ are both rational or irrational. Does this also mean that with$\displaystyle\lim_{n \to +\infty} f(n)=\lim_{n \to +\infty} ...
0
votes
1answer
17 views

Recurence Problem. - Solve either by substitution or Expansion

Function T(n) is defined by the following recurrence relation: $$ T(n)=2T(\lfloor\sqrt{ n}\rfloor)+\log(n) $$ $$ T(0)=1 $$ How would I Solve by substitution and/or Expansion? Note: ...
1
vote
2answers
43 views

Estimating the behavior for large $n$

I want to find how these coefficients increase/decrease as $n$ increases: $$ C_n = \frac{1}{n!} \left[(n+\alpha)^{n-\alpha-\frac{1}{2}}\right]$$ with $\alpha=\frac{1}{br-1}$ and $0\leq b,r \leq 1$. ...
0
votes
1answer
21 views

$g(f(n))\in o(g(n)/n)$ for any $f(n)\in o(n)$

Let $f:\mathbb{N}\rightarrow\mathbb{R}$ be a function such that $f(n)\in o(n)$. Is it always possible to find a function $g:\mathbb{N}\rightarrow\mathbb{R}$ such that $g(f(n))\in o(g(n)/n)$? I'm ...
1
vote
1answer
13 views

$g(n)\in\omega(n^r)$ but $g(f(n))\in o(n^{r-1})$

Let $f:\mathbb{N}\rightarrow\mathbb{R}$ be a function such that $f(n)\in o(n)$. Is it always possible to find a function $g:\mathbb{N}\rightarrow\mathbb{R}$ and a constant $r>1$ such that ...
0
votes
1answer
22 views

Big-Oh Notation and Solving for f(x)

Taking Discrete Mathematics and completely lost when it comes to Big-Oh Notation. While I know it's used to profile code I can't figure out how to solve the following problem: Find the least integer ...
6
votes
2answers
77 views
+50

Infinite Sum of Sines With Increasing Period

A while ago, I was thinking about the Weierstrass function, which is a sum of sines with increasing frequencies in such a way that the curve is a fractal. However, I wondered what would happen if one ...
1
vote
3answers
36 views

O-Notation: How to put the function in order.

I am new here, so I am sorry for any mistake that I'll probably make. I have an exercise to solve, but I didn't really understand how this really works. I am given the functions $2^n$, $n^{0.01}$, ...
9
votes
2answers
126 views
+50

An asymptotic expression of sum of powers of binomial coefficients.

Let $k$ be a fixed positive number and $n$ an integer increasing to infinity. Then $$\sum_{\nu =0}^n \binom{n}{\nu}^k \sim \frac{2^{kn}}{\sqrt{k}} \left( \frac{2}{\pi n} \right)^{\frac{k-1}{2}}.$$ ...
0
votes
0answers
17 views

asymptotic esimation of a complex integral

I am searching for a general method to evaluate asymptotically this kind of integral $\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}f(q,\omega)\exp[-\mathrm{i}kr]\exp[-\mathrm{i}\omega ...
3
votes
5answers
97 views

When $a\to \infty$, $\sqrt{a^2+4}$ behaves as $a+\frac{2}{a}$?

What does it mean that $\,\,f(a)=\sqrt{a^2+4}\,\,$ behaves as $\,a+\dfrac{2}{a},\,$ as $a\to \infty$? How can this be justified? Thanks.
1
vote
1answer
41 views

Prove or disprove: $ \frac{3x^3+2x+1}{x+2} $ is $ \theta (x^2) $.

Prove or disprove: $ \frac{3x^3+2x+1}{x+2} $ is $ \theta (x^2) $. I know that $f(x)$ is $\theta (g(x)) $ if it is both $ O(g(x)) $ and $\Omega (g(x))$ when $ x > n$ I reasoned that $f(x)$ is ...
1
vote
1answer
35 views

Bound for sum of products

Given are $x_1,\ldots, x_n\in \{0,1,\ldots,n\}$, $y_1,\ldots, y_n\in \{0,1,\ldots,n\}$ with the property that $$\sum_{i=1}^{n}{x_i}\leq B,$$ $$\sum_{i=1}^{n}{y_i}\leq B$$ Let's assume that $B$ is ...
2
votes
1answer
64 views

Challenging Algorithms Question: Proving that upper bound for computing 'silhouette' points is nlog(n)

Given a set of points (on the left). The silhouette set of these points is shown to the right. In this problem, all rectangles are defined by two points, $(0, 0)$ and $(x_i, x_j)$. Formally, for a ...
1
vote
1answer
56 views

Help with using Master Theorem on $T(n)=9T(n/3) + \Theta(n^2/\operatorname{lg}(n))$

I want to use the Master theorem to solve the following recurrence. $$T(n)=9T(n/3) + \Theta(n^2/\operatorname{lg}(n))$$ We can easily see that $a=9$ and $b=3$ and $f(n) = n^2/\operatorname{lg}(n)$. ...
0
votes
1answer
25 views

A Question Regarding Asymptotic Notations

Well, here I am again, stuck with my algorithm's class HW question again... . $g(n) = \Theta(n^2)$, $f(n) = g(n) + g(n-1) + ... + g(2) + f(1)$ Given the conditions above, is it suitable for me to ...
1
vote
1answer
13 views

Find functions which change asymptotic properties if raised to 2

Kindly give an example of positive functions f(n) and g(n) such that f(n) = O(g(n)) but it does not hold that 2^f(n) = O(2^g(n)). A friend asked this question as this came in one of his ...
1
vote
3answers
31 views

For small $z, (1 + z)^{−2} \sim 1 − 2z$…

I came across the following statement while reading Holmes book on Perturbation Methods - To reduce the differential equation, recall that, for small $z, (1 + z)^{−2} \sim 1 − 2z$ I don't know ...
1
vote
2answers
82 views

Growth of $\sum_{x=1}^{n-1} \left\lceil n-\sqrt{n^{2}-x^{2} } \right\rceil$

I'm interested in the growth of $$f(n):=\sum_{x=1}^{n-1} \left\lceil n-\sqrt{n^{2}-x^{2} } \right\rceil \quad \text{for}\quad n\rightarrow\infty $$ Progress (From comments) I've got ...
3
votes
0answers
26 views

How can one derive Stokes lines of the Stokes phenomenon of asymptotics from a differential equation?

Is there a standard technique to calculate Stokes lines and anti-Stokes lines of the Stokes phenomenon of asymptotics for a function defined as the general solution to a differential equation without ...
0
votes
1answer
12 views

Asymptotic $T(n)=T(\sqrt{n})+1$

I would like to find the complexity of $T(n)=T(\sqrt{n})+1$ I did : $$T(n)=T(\sqrt{n})+1$$ $$T(n)=T(n^{1/2})+1$$ $$T(n)=(T(n^{1/4})+1)+1=T(n^{1/4})+2$$ And after $k$ steps : ...
0
votes
0answers
25 views

Efficiently calculating the 'prime-power sum' of a number.

Let $n$ be a positive integer with prime factorization $p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m}$. Is there an 'efficient' way to calculate the sum $e_1+e_2+\cdots +e_m$? I could always run a brute ...
0
votes
0answers
11 views

Asymptotic results for functions of order statistics

There are $n$ ($n \ge 3$) iid random variables $\{ {c_i}\} _{i = 1}^n$ on the interval $[\underline c,\bar c]$ ($\underline c>0$). The cdf $F(\cdot)$ and pdf $f(\cdot)$ are unkown to us, but we ...
2
votes
0answers
30 views

Find $f(n)$ in $\binom {2^n} {n^4} = (f(n)+ o(1))^n$

Task is to find $f(n)$ in the following equation: $\binom {2^n} {n^4} = (f(n)+ o(1))^n$ I've found that the problem is a bit over my head. I'm attaching my partial solution below: With use of the ...
2
votes
1answer
41 views

terminology relating to o(1)

If someone says, for example, "I have an algorithm that runs in time $n^2+\varepsilon$ for any constant $\varepsilon>0$", the interpretation for this statement seems to be that for any constant ...