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
23 views

Find the angle between asymptotes

Sketch the locus of the centres of circles which touch two fixed and unequal circles. Find the angle between the asymptotes How shall I find the locus when the size of the circles are not ...
2
votes
2answers
24 views

How to find Big O notation here.

How can I express the formula (logn + 2)*(n - 1) using big-O notation My try:- (logn + 2)*(n - 1) => nlogn + 2n - logn - 2. Now I am confused whether this is O(n) or O(log n)
2
votes
1answer
23 views

Determining a succinct big $\Theta$ expression [on hold]

Determine a succinct big-$\Theta$ expression for the growth of function $$ (\log^{50}n)n^2 + n^{2.1}(\log n^4) + 1000n^2 + 100000000n $$
0
votes
1answer
15 views

Proving the asymptotic relationship between $(lg\cdot n)^{0.5}$ and $lg\cdot (n^{0.5})$?

Say $f(n) = (lg\cdot n)^{0.5}$ and $g(n) = lg\cdot (n^{0.5})$ It would appear that $f(n) = O(g(n))$ for $n \gt 55$ correct? How do I go about proving the the relationship for this?
0
votes
0answers
18 views

Asymptotic notations (Big Omega) [on hold]

Use the definition of big- $\Omega$ to prove that $n + n(\log n)^2 = \Omega(5n + 9n(\log n)^5)$. Provide the appropriate $c$ and $k$ constants ? I am new to the topic : Advanced Analysis of ...
-2
votes
1answer
33 views

Show $n + n^2 \mathcal O(\ln (n))= \mathcal O(n^2 \ln (n))$ [on hold]

Show that $$n + n^2 \mathcal O(\ln (n))= \mathcal O(n^2 \ln (n))$$
0
votes
2answers
76 views

prerequisit for BigO notation

I have been trying to learn algorithms for a long time now and I am really struggling with the math part and don't know what to do. I only know very basic math, so my question is what do I have to ...
1
vote
0answers
16 views

A Question from Murray - Asymptotic Analysis

I'm stuck on one of the questions related to the method of stationary phase in Murray's book on Asymptotic analysis. The question is as follows; If $h(t)$ has a single stationary point at $t_0$, ...
0
votes
0answers
19 views

Big $O$ question for While and For loops [on hold]

I have to find the exact $O(N)$ for these instructions, not just the order of magnitude. I'm not getting any of the answers provided for me. I know the first loop is $O(3N+2)$. The declaration of ...
-1
votes
2answers
20 views

Arrange the following growth rates in increasing order O((35)^n),O(n^4),O(1),O(n^3 logn) [duplicate]

I want to Arrange the following growth rates in increasing order This order are following : O((35)^n),O(n^4),O(1),O(n^3 logn) Please give me idea how to arrange growth rates in increasing order
0
votes
0answers
31 views

Understanding $\Theta$-notation rigorously

Let $f$ and $g$ be functions on $\mathbb{N}$. If $f(n) \in \Theta(g(n))$, we say that (for sufficiently large input) "the function $f(n)$ is equal to $g(n)$ to within a constant factor". What does ...
2
votes
0answers
36 views
+50

Name for kind of big O notation with leading coefficient

Context: As known the big O notation $O(f(n))$ describes a function $g(n)$ such that there is a constant $C \ge 0$ with $\limsup_{n\to\infty} \left|\frac{g(n)}{f(n)}\right| \le C$ (I assume that ...
-1
votes
1answer
26 views

Show that $f(n)$ is $O(g(n))$ then $f(n)+c$ is $O(g(n))$ [on hold]

Show that $f(n)$ is $O(g(n))$ then $f(n)+c$ is $O(g(n))$ for all constants $c$. In our class, $$O(g(n)) = \{f(n) \mid \exists C,n_0 \colon \forall n \geq n_0 \colon |f(n)| \le C|g(n)| \}$$
1
vote
3answers
36 views

$O( n^3)$ vs $O(n^2 \ log n)$

I was wondering how $n^3$ compares to $2n^2 \log n$ as I thought that $n^3$ is $\Omega(n^2 \log n)$ but there is the fact that $n$ is $O(n \log n)$ so I wasn't sure whether it is bigO or $\Omega$
0
votes
1answer
33 views

What is the big Oh notation for the following series.

I have the series $1+3+9+27+... + 3^n$ . I need to find the Big O solution. What I have tried. The above series is a Geometric Progression with r=3. SO the sum would be. $ [1* 3^{n+1} - 1]/2 $ How ...
1
vote
0answers
17 views

asymptotic of an interesting recurrence realtion (more general case)

A link to the original question for reference:Click here I tried to study a more general situation: Let $y_{d,d}=1$ and $$ ...
0
votes
1answer
51 views

Simplifying $f(x) = \left(x^{3} + 2x^{2} + O(x)\right)\cdot\left(1 + \frac{1}{x} + O\left(\frac{1}{x^{2}}\right)\right) $

Simplify $$f(x) = \Big(x^{3} + 2x^{2} + O(x)\Big)⋅\Bigg(1 + \frac{1}{x} + O\bigg(\frac{1}{x^{2}}\bigg)\Bigg) $$ as $x \to +\infty$. I am a bit stuck as to what to do with the three sets of ...
0
votes
0answers
16 views

Comparing functions

I wanted to make sure I had the correct understanding of the following big $O/\Theta/\Omega$ questions and I figured it would be better posted here than SO as it was more about comparing function. a) ...
0
votes
0answers
16 views

“Asymptotic” $\mathbb{R}$-algebras

Definition. By an asymptotic $\mathbb{R}$-algebra, I mean an $\mathbb{R}$-algebra $F$ of functions $\mathbb{R} \rightarrow \mathbb{R}$ satisfying: $$\mathop{\forall}_{f:F}\left[\left(\lim_{x ...
0
votes
0answers
18 views

What do we call the number that measures how good of an asymptote $g$ is to $f$, and what are the basic results about this number?

Suppose we have a (potentially very complicated) smooth function $f : \mathbb{R} \rightarrow \mathbb{R},$ and we're trying to approximate it (in the limit as the input value goes to $+\infty$) by a ...
1
vote
1answer
18 views

Large pairwise coprime sets

Say that a set $S\subseteq\Bbb N$ is pairwise coprime if every two elements of $S$ are relatively prime. Denote by $f(n)$ the size of a maximal pairwise coprime subset of $\{1,...,n\}$. What is ...
1
vote
1answer
24 views

Product property of Big O

Trying to prove: If $f(n)$ and $g(n)$ are both $O(h(n))$, then $f(n)*g(n)$ is $O(h^2(n))$. Understanding so far : The product of upper bounds of functions gives an upper bound for the product of ...
4
votes
1answer
60 views

Each number in $S\subseteq \{1,\ldots,2n\}$ does not divide another one, with $|S|= n$. In how many ways?

Let $f(n)$ be the number of subsets $S\subseteq \{1,2,\ldots,2n\}$ such that $|S|=n$ and $a$ does not divide $b$ whenever $a,b \in S$ are distinct. Can we evaluate $f(n)$, at least asimptotically? ...
0
votes
1answer
19 views

Asymptotic error expansion of global error for single step methods

My question refers to the proof of the following theorem, but it may suffice to just skip the theorem and continue with the problematic taylor expansion $(\ast)$: Let $f(t,y)$ and the single step ...
0
votes
2answers
47 views

How to show that $O(n^\frac{3}{4} \log n) = O(n)$?

I try to analyze LazySelect algorithm (finds kth order statistic of a set). One of the steps is to take a sample of $n^\frac{3}{4}$ elements and sort it. It seems like this sorting is linear relative ...
2
votes
0answers
61 views

Arithmetic progression of squarefree integers?

Let $x$ be a given positive integer. I'm intrested in the longest arithmetic progression of squarefree integers within the interval $(x,x^2)$. Both constructive and nonconstructive results. For ...
1
vote
2answers
59 views

Why is $\binom{2n}{n} \asymp \Theta \big(\frac{2^{2n}}{\sqrt{n}}\big)$?

I saw this statement : $$\binom{2n}{n} \asymp \Theta \bigg(\frac{2^{2n}}{\sqrt{n}}\bigg) \asymp \Theta\bigg(\frac{4^n}{\sqrt{n}}\bigg)$$ How did we go from the first statement to the second? I tried ...
2
votes
1answer
40 views

Estimate integral $\,\displaystyle\int_{0}^{\infty}\operatorname{sech}\left(\varepsilon x\right)\cos\left(kx\right)\,dx,\,$ with $\,k,\varepsilon>0$

$ \newcommand{\sech}{\operatorname{sech}} $ Is there any analytic/asymptotic way to estimate the value of the integral: $$ \int_{0}^{\infty} \sech\left(\varepsilon x\right)\cdot ...
1
vote
0answers
15 views

what happens when expansion parameter is of the order of dynamical variable itself?

Lets consider following differential equation, $\epsilon \frac{dy}{dt} = ....$ In principle one can use Method of matched asymptotic expansion or Method of multiple scales to solve such singular ...
1
vote
3answers
72 views

Missing steps: Show the sum of the first n positive integers is of order $n^2$

In Rowsen's Discrete Mathematics text, 6th edition. He has this problem as an example (#11) on page 190. His solution for obtaining a lower bound is to ignore the first half of the terms. He does the ...
3
votes
1answer
64 views

Does writing $f(x)\sim \ell$ have a sense?

If $\lim_{x\to a}f(x)=\ell$, is it correct to say that $f(x)\sim_a \ell$ ? I would say yes since $\lim_{x\to a}\frac{f(x)}{f(a)}=1$, but on a test I wrote $e^{-t}\sim_0 1$ and the corrector said that ...
2
votes
2answers
29 views

Asymptotic of $ \sum_{r=1}^{k} \frac1{r^{3/2}}$ - Generalized Harmonic Number

What is the asymptotic approximation of the following generalized Harmonic number as $k \to \infty$ ? $$H(1.5,k) = \sum_{r=1}^{r=k} \frac{1}{r^{1.5}}$$ (there is a similar question posted on ...
-2
votes
2answers
31 views

specifying an asymptotic function

Please help me out; I need to specify a function satisfying these conditions: $$ f(0)=1 \;\;;\;\lim_{x \to \infty}f(x)=0$$ Hopefully does there exist a simple answer? Thanks a lot!
2
votes
0answers
50 views

Approximate an integral with Bessel functions

Given $r,a,\lambda\in\mathbb{R}$, $r<a$, how can I find an approximate solution for the following definite integral? $$ \int_0^\infty J_0 (\lambda r)J_1(\lambda a)\frac{1}{\sqrt{n+\lambda^2 ...
1
vote
2answers
34 views

oblique asymptote problem

I can't resolve limit for oblique asymptote for: $$\frac{2x^2 e^{1/x}}{2x+1}-x$$ I've tried solving it by putting the common denominator but it's a bit confusing because the numerator is bigger then ...
0
votes
0answers
23 views

Simple question about asymptotic notation

I'm quiet new to the asymptotic world, so apology in advance if this question seems too trivial for you experts. Given $\frac{2kn2^{-k}}{E[X]}.$ As $k \sim 2\text{log}_{2} n$, the numerator is ...
0
votes
0answers
41 views

For any arithmetic progression $n \in \Bbb{N} : n \equiv b \pmod a$, the natural density is $\frac{1}{a}$?

This question comes from here (page 10). Given that $d(A) := \lim_{x\to\infty}\frac{1}{x}\sharp\{n \leq x : n \in A\}$, how do I get that: 1) $d(n \equiv b \pmod a) = \lim_{x\to\infty}(\left [ ...
0
votes
0answers
29 views

How to prove $x^m = O(e^x)$ for any $m \gt 0$?

My attempt: It's true for $m = 1$ clearly. Now assume true for $m=1\dots M-1$. Then $x = O(e^x)$ and $x^{M-1} = O(e^{M-1})$. Lemma: if $f = O(g)$ and $f' = O(g')$ then $ff' = O(gg')$. Proof: $f = ...
1
vote
2answers
31 views

Simple question, what is meant by 'as $x \to \infty$ the number of squares $\leq x$ is $\sqrt{x} + O(1)$?

For $x \to \infty$: the number of squares $n^2 \leq x$ is $\sqrt{x} + O(1)$. From here (page 6). More specifically, do they mean that... I'm confused now. I'm really not sure what they mean ...
3
votes
1answer
61 views

Calulate a limit involving $\zeta{(\zeta{(z)})}$

I'm currently trying to evaluate the following limit: $$ \lambda=\lim_{z\to\infty}{\left[2^z-\left(\frac{4}{3}\right)^z-\zeta{(\zeta{(z)})}\right]} $$ A look at numerical approximations suggests, that ...
-2
votes
0answers
50 views

BIG OH:$ f (x) = 3x^3 + 2x + 4$. One has

I have this question in my homework. Its an a multiple choice question and goes as following: Let $f (x) = 3x^3 + 2x + 4$. One has that $O(x^3)$ ** the answers have been checked with the teachers ...
3
votes
1answer
33 views

$\sum_{n \leq x} \frac{1}{n} = \int_{1}^x \frac{dt}{t} + O(1)$ help deriving it

On page 5 of: Probabilistic Number Theory by Dr.J¨orn Steuding, there's $\sum_{n=2}^{[x]} \frac{1}{n} \lt \int_{1}^{[x]} \frac{dt}{t} \lt \sum_{n=1}^{[x] - 1}$ Therefore integration yields: ...
0
votes
0answers
24 views

The function $g(x)$ is in $\Omega(x^c)$ as $x\rightarrow 0$ for all $c>0$. Does this imply that $\lim \inf_{x\rightarrow 0} g(x) > 0$?

Consider a function $g: \: \mathbb R^+ \mapsto \mathbb R^+ $. For any $c>0$ this function is in $\Omega(x^c)$ as $x\rightarrow 0$. That is, given $c>0$ there exist $L$ and $x_0$ such that $g(x) ...
7
votes
0answers
98 views

Bear of an integral

I have a pretty ferocious integral to solve, and would be over the moon if I were able to get some sort of analytic expression / insight for it. $$ I = \int_{r}^{\infty} r_0^{-5/2} W_{-i\alpha'/2, ...
10
votes
1answer
76 views

Asymptotic behaviour of log log sum

I am interested in the asymptotics of $$F(m) := \prod_{j=1}^m \log(j+1) = \exp\left(\sum_{j=1}^m \log \log(j+1) \right)$$ Is there anything known? If not I figure I will need some good bounds on the ...
1
vote
1answer
54 views

Asymptotic for $\int_{\mathbb{R}}e^{ik(sin x - x)}f(x)\, dx$

Suppose $f$ is a smooth compactly supported function supported in $[-\pi, \pi]$. The problem I am working on is to show that $$\int_{\mathbb{R}}e^{ik(\sin x - x)}f(x)\, dx = ...
2
votes
1answer
66 views

Upper bounding a tricky sum

For a problem in probability, I'm trying to find an upper bound for $$ \sum_{d=0}^k\binom{k}{d}\gamma^d(1-\gamma)^{k-d}\left(1-p^d(1-p)^{k-d}\right)^m$$ which will help me analyze what values of ...
0
votes
1answer
47 views

How to prove that $\left(\log \log n\right) \times \left(\log \log \log n\right) = Ω\left(\log n\right)$

Is $$\log \log n \times \log \log \log n = \Omega(\log n) $$ How can we prove it. Actually I'm trying to prove that $f(n) = \lceil(\log \log n)\rceil !$ is polynomially bounded. It means $$c_1 ...
0
votes
2answers
29 views

Prove or disprove the following asymptotic relations

$P(x) = 2^x$ Prove or disprove that $p(n^3 + 4) \in O\left(p\left(n^3\right)\right)$ $2^{(n^3 + 4)} \in O(2^{n^3})$ $\lim_{n \rightarrow \infty} \space \frac{2^{n^3 + 4}}{2^{n^3}}$ using ...
0
votes
0answers
19 views

Asymptotic form of Whittaker function

I am working with Whittaker functions for a project and have no experience with asymptotic analysis - how is the following expression, for $\kappa \rightarrow \infty$ through the real numbers ...