2
votes
0answers
42 views

perturbation theory solution of forced Duffing's equation

Question: Find the leading order of the asymptotic expansion for large t: $\frac{d^2x}{dt}+\varepsilon\beta\frac{dx}{dt}+x+\varepsilon x^3=Fcos(\frac{1}{3}\big(1+\varepsilon\omega)t\big)$ I have ...
0
votes
1answer
27 views

Big-O Analysis: Max Bounded by the Sum

I have been asked to show that: $$ \mathcal{O}(Max\{ f(n), g(n) \}) = \mathcal{O}(f(n) + g(n)) $$ I have seen explanations of similar problems, but this is the first time I have encountered the ...
2
votes
2answers
106 views

Calculate limit with factorial

I need to find the limit of this function..I thought about L'hôpital's rule, but can't seem to derive them both.. $$\lim_{n\rightarrow\infty} \frac{(2n)!}{(n!)^2}$$
0
votes
0answers
22 views

Determine the realtions ($\mathcal{O}$,$\Theta$,$\Omega$ ) between $f(n) = \ln(n^{c} + n^{d})$ and $g(n)=\ln(n^{a} + n^{b})$

I am trying to determine the realtions ($\mathcal{O} $,$\Theta$,$\Omega$ ) between : $$f(n) = \ln(n^{c} + n^{d})$$ $$g(n)=\ln(n^{a} + n^{b})$$ Note: $a,b,c,d>0$ I need some advice how to use the ...
1
vote
1answer
45 views

Need help in finding the asymptotic variance of an estimator.

I kinda doing some review questions for my finals and I kinda got stuck on this question. I'm able to do part a by finding the maximum likelihood estimator but for some reason. To find the ...
2
votes
1answer
39 views

Leading order approximation to differential equation

Find a leading order approximation to the solution of $\epsilon y'' + 2 y' + e^y = 0$, $y(0)=y(1)=0$ as $\epsilon \to 0$. I know there is a boundary layer near $x=0$ and not at $x=1$ so I can ...
2
votes
0answers
22 views

Prove or disprove the Big-O of an exponential function

$f(n) = 2^{n+1} = O(2^n)$ Intuitively, I think the statement is false. However, when I go about disproving it, I find that $2^{n+1} = 2^n \cdot 2$, meaning that if there is a constant $C$ larger than ...
0
votes
1answer
30 views

Asymptotic behaviour of a couple of special functions (features exponentials and logarithms)

I'm dealing with a couple of functions: $n \log n$, $( \log \log n)^{ \log n}$, $( \log n)^{ \log \log n}$, $n e^{\sqrt{n}}$, $( \log n)^{ \log n}$, $n 2^{ \log \log n}$, $n^{1+1/( \log \log ...
1
vote
1answer
39 views

Question about Big O Notation

I don't seem to understand big-O notation very well. If someone would explain it to me as well as explain how this problem would work Let f(n) = (3$^n$$^+$$^1$ - 3)/2. For each of the following ...
4
votes
1answer
70 views

Applications of the Exponential Integral?

this is my first time asking a question on here so please forgive me if I have made any formatting mistakes. I have the integral $f(x) = \int_0^\infty \frac{e^{-t}}{x + t} \; dt$ and I have shown the ...
1
vote
1answer
31 views

Power Iteration method for eigenvalues - Show the error is bound

Let $A \in $Sym$_{n}(\mathbb R)$ with eigenvalues $\lambda_i$ such that $|\lambda_1| > |\lambda_2| \geq |\lambda_3 |\geq ... \geq |\lambda_n|$ We define the following process as "Power Iteration": ...
0
votes
2answers
39 views

Discrete Mathematics: Prove that f(x) is in O(x)

Prove that $$\frac{2x^{2}+x}{x+1}$$ is in $O(x)$
-1
votes
1answer
44 views

Prove that |O(2n)-O(n)|=O(n)

I need to prove that statement with the defenition of big O |O(2n)-O(n)|=O(n) Does it can be proven? or not? if i can, so how..in which way? i tried almost ...
0
votes
1answer
22 views

Prove the following $\frac{\Omega(f(n))}{\Omega(g(n))} \subseteq \Omega(\frac{f(n)}{g(n)})$

I want to prove the following: $$\frac{\Omega(f(n))}{\Omega(g(n))} \subseteq \Omega(\frac{f(n)}{g(n)})$$ I wonder if its true? What about using $n$ and $n^2$? Any suggestions? Thanks!
0
votes
1answer
31 views

Order functions by speed of their asymptotic growths

We are given list of functions. Task is to sort it by the speed of their asumptotic growth in ascending order. Yes, it's a homework. I already spent some solid amount of time calculating limits. I ...
0
votes
1answer
67 views

Prove $\Omega(f(n)) \subset \Omega(g(n)), iff : g(n)\in \mathcal{O}(f(n)) \wedge f(n) \not\in \mathcal{O}(g(n))$

I want to prove the following $$\Omega(f(n)) \subset \Omega(g(n)), iff : g(n)\in \mathcal{O}(f(n)) \wedge f(n) \not\in \mathcal{O}(g(n))$$ What I did so far is: $$t(n)\in\Omega(f(n)) \rightarrow ...
0
votes
0answers
15 views

How to compute an asymptotic expansion for $\sum_{i \ge 0} a_in^{-i} $ to a relative error of $O(n^{-2})$? [duplicate]

How to compute an asymptotic expansion for $\sum_{i \ge 0} a_in^{-i} $ to a relative error of $O(n^{-2})$
0
votes
2answers
25 views

$$\\|O(2n) - O(n)|=O(n)$$

I need to prove or contradict:$$\\|O(2n) - O(n)|=O(n)$$ I try: $$\\f(n)=1.5n\in O(2n),g(n)=0.25n\in O(n),h(n)>0\in O(n) : \\ |1.5n - 0.25n|=h(n)\\1.h(n)=1.25n \in O(n)\\ but: 2. h(n)=-1.25n \notin ...
0
votes
0answers
34 views

Relations between stochastic Big O-Notation, limsup and lim?

I have to solve a list of exercises on probability theory but I'm having several problems in understanding the following questions; could you help me? Thank you! Let $||.||$ indicate the Euclidean ...
1
vote
1answer
37 views

Prove the following $\Omega(n\cdot f(n)) = n\cdot \Omega(f(n))$

I want to prove the following by definition of asymptotic notation $$\Omega(n\cdot f(n)) = n\cdot \Omega(f(n))$$ Any suggestions?
0
votes
1answer
39 views

Show that $f(n) = 2n^4 + 4n^2 + 5$ has a tight bound of $\Theta(n^4)$

What I have done so far (planning on showing lower and upper bound first): Lower bound: $$c_1n^4 \leq 2n^4 + 4n^2 + 5$$ Divide by $n^4$ $$c_1 \leq 2 + \frac{4}{n^2} + \frac{5}{n^4}$$ Take limit as ...
0
votes
0answers
60 views

Finding the Probability Limit and Asymptotic Distribution of Xbar-LogYbar

I'm kinda still new to Large Sample Theory and I have already attempted the question. Not sure if I did it right. Based on Kinchin , I know Xbar converges in probability to mu and Ybar converges in ...
1
vote
1answer
37 views

$\ln(f(n))\in \theta(\ln(g(n)))$ Its true that: $(g(n))^{f(n)}\in \theta((f(n)^{g(n)})$?

I want to prove the following: $\ln(f(n))\in \theta(\ln(g(n)))$ Its true that: $$(g(n))^{f(n)}\in \theta((f(n)^{g(n)})$$ How I can use $\ln$ function to prove it? prove by definition its ...
0
votes
1answer
82 views

$|f(n)-g(n)|\in \mathcal{O}(t(n)) $ And $f(n)+g(n)\in \Omega(t(n))$,Its true that $f(n)\in \Omega(t(n))$?

I want to prove the following by the definition $$|f(n)-g(n)|\in \mathcal{O}(t(n)) $$ $$f(n)+g(n)\in \Omega(t(n))$$ Its true that $f(n)\in \Omega(t(n))$? What I tried is just think about ...
0
votes
1answer
48 views

Big O: Prove that for all $x \leqslant y$, $n^x \in \mathcal O(n^y)$

For all real numbers, if $x \leqslant y, n^x \in \mathcal O(n^y)$. This is a homework question, so I'm just looking for a little guidance with this question, and not the answer. I understand how to ...
1
vote
0answers
86 views

Asymptotic estimate of coprime pairs of integers $\leq n$.

Let $M_{n} = \{(x,y) \in [n] \times [n]: xy \leq n^{2} \text{ and } gcd(x,y) = 1\}$, where $[n] = \{1, 2, \dots , n\}$. In other words, let $M_{n}$ be the set of pairs of coprime integers both $\leq ...
1
vote
1answer
71 views

Solve $\epsilon x^3-x+1=0$

I'm trying to find the expansion for the roots of this equation. I've found one root as $x\sim 1+\epsilon $. Now considering the dominant balance I want to rescale so that $\epsilon x^3\sim O(x) ...
0
votes
1answer
57 views

$\frac{1}{n} \sum_{k=1}^{n-s} X_{k+s}X_{k}$ the same as $\frac{1}{n} \sum_{k=1}^{n} X_{k+s}X_{k}$ for $n \rightarrow \infty$?

I need to show that $$ \frac{1}{n} \sum_{k=1}^{n-s} X_{k+s}X_{k}$$ for some number $s$ is essentially the same (asymptotically negligible) as $$ \frac{1}{n} \sum_{k=1}^{n} X_{k+s}X_{k}$$ as $n ...
1
vote
2answers
77 views

Prove that $a^n$ is $O(n!)$.

I proved by induction that $2^n = O(n!)$. Can this fact be used to prove the following: Let $a$ be a positive constant and $n$ be a natural number. Show that $a^n=O(n!)$. I have already ...
1
vote
0answers
36 views

Question about asympotic expansions!! please help!

Question: Find the constants $$a_0, a_1, a_2$$ in the asympotic expansion $$\int_0^x t\sqrt{ln(t)} dt$$ = $a_0(x^2)(lnx)^\frac 12$ + $a_1\frac {x^2}{(lnx)^\frac 12}$ + $a_2\frac {x^2}{(lnx)^\frac ...
0
votes
1answer
71 views

Time efficiency of brute force algorithm as a function of number of bits?

This is homework help so advising how to solve such a problem is appreciated. The question reads as follows: What is the time efficiency of the brute-force algorithm for computing $a^n$ as a ...
2
votes
2answers
77 views

Prove that $\mathcal{O}(f_{1}(x)+ \dots +f_{n}(x))= \mathcal{O}(\max(f_{1}(x), \dots ,f_{n}(x)))$

I want to prove the following that based on maximum rule of functions: $$\mathcal{O}(f_{1}(x)+ \dots +f_{n}(x))= \mathcal{O}(\max(f_{1}(x), \dots ,f_{n}(x)))$$ the base prove is for each 2 functions ...
0
votes
0answers
73 views

Order functions by their growth according to big-O notation

Since this is my homework, I'm not asking for the complete solution. Could you please just look through my solution and show me my errors, or give some advice what has to be corrected? I've looked ...
2
votes
2answers
81 views

Is it true that $(2^n+n^2)(n^3+3^n)$ is $O(6^n)$?

$(2^n+n^2)$ is $O(2^n)$ and $(n^3+3^n)$ is $O(3^n)$, therefore I conclude that $(2^n+n^2)(n^3+3^n)$ is $O(2^n*3^n)=O(6^n)$
1
vote
2answers
32 views

Properties that hold when $f = \mathcal{O}(g)$

This is a homework problem. There are two questions where the answers seem intuitive, but even if I were correct in assuming they were true, I'd still need to provide a proof: When $f(n) = ...
6
votes
3answers
96 views

Show that $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Theta(3^n)$

In this question we are asked to show that $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Theta(3^n)$ What I did: $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \sum_{k=2012}^{n} 2^k*1^{n-k}\binom{n}{k} \leq ...
2
votes
1answer
52 views

Show that $\operatorname{ln}(n!)=\Theta(n\operatorname{ln}(n))$

Another question about asymptotic approximations. We are asked to show that $\operatorname{ln}(n!)=\Theta(n\operatorname{ln}(n))$ I'm stuck tho and can use help. What I did is: ...
0
votes
0answers
33 views

check my short simple proof - Functions are of same magnitude. Asymptotic notation.

A simple question with a short solution I thought of, but I would like verification. $f(n)$ is a function that approaches infinity as $n$ approaches infinity. We are asked to show that ...
0
votes
1answer
35 views

Check my short proof - asymptotic approximation, which function is bigger

The goal of this exercise is to show that $\ln(n+1)-\ln(n) = O(\frac{1}{n})$ what I did is: I used the fact that if $f=O(g)$ then $\frac{f}{g}=O(1)$. $\ln(n+1)-\ln(n)=\ln(\frac{n+1}{n}) = \ln(O(1))$ ...
2
votes
1answer
37 views

Problem finding limit - which function is asymptotically larger

I have a homework question, so please don't answer fully but I would appreciate a push in the right direction. Basically we need to figure out if $n^{n+\frac{1}{2}}e^{-n}$ is larger,smaller, or equal ...
0
votes
1answer
44 views

Big - Oh proof $n^{2^n} = O(2^{2^n})$

But the book asks me to prove that it's correct: $$n^{2^n} + 6*2^n = O(2^{2^n})$$ But I think, it's an incorrect one. Because, it's correct only for $n < 2$.
1
vote
0answers
30 views

How to find the influence function of $\int_{[0,t]}(1-F_\_)^{-1}dF$,i.e., cumulative hazard function

The common strategy is to replace $F$ with $(1-t)F+t\delta_x$ and then expand the integral. However, I am not sure how to deal with $F_\_$. It seems different from $F$.
1
vote
0answers
39 views

How to prove that $\sum_{p \leq x} {\log p \over p} = \log x + O(1)$? [duplicate]

Problem Prove that $$ \sum_{p \leq x} {\log p \over p} = \log x + O(1) $$ as $x \to \infty$. Notes: $p$ ranges over primes, $\log$ is natural Progress Using Riemann-Stieltjes integration and ...
5
votes
1answer
146 views

How to prove this inequality $\pi(x) > \log x - 1$ involving the prime counting function?

Problem Prove that $\pi(x) > \log x - 1$. Progress Based on a hint and very elementary methods, I got that $$ \prod_{p \leq x} (1-p^{-1})^{-1} \leq \prod_{k=2}^{\pi(x)+1} (1-k^{-1})^{-1}. $$ The ...
5
votes
1answer
111 views

Obtaining the Airy kernel from the Christoffel-Darboux formula with asymptotic Hermite polynomials

Let the Kernel associated to a family of orthogonal polynomial $p_n(x)$ with weight $w(x)$ be defined as $$K_N(x,y):=\frac{\sqrt{w(x)w(y)}}{\int w(x) p_{N-1}(x)p_{N-1}(x)dx} ...
1
vote
1answer
45 views

How to prove that sum given by generating function diverges for given value of $x$

I have a generating function: $A(x)=\dfrac{3-8x}{1-4x+6x^2-3x^3}$ (also I have a recurrence from which this function is built). I have to prove that sum $\sum\limits_k a_k\left(\dfrac{4}{3}\right)^k$ ...
3
votes
0answers
79 views

Asymptotic solution for $T(n) = 6T(n/4) + n \lg n$

I am given that $T(n) = 6T(n/4) + n \lg n$ and want to find $\Theta(T(n))$. Below is what I have typed up for my solution so far; I asked my professor because I was unsure as to how I could assure ...
1
vote
0answers
54 views

Find asymptotics in a given form $n=(e+o(1))^{f(s)}$

Let $p\to\infty$, $s={\binom {p^4} p}$ and $n={\binom {p^4}{p^2}}$. Find a function $f(s)$ in the following form $$\large n=(e+o(1))^{f(s)}$$ I've tried to use the followinf asymptotics for ...
3
votes
1answer
107 views

Find the constant $c$ in the equation $\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$

Find the constant $c$ in the equation $$\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$$ I've tried to use this asymptotics $$C_n^k \sim \frac{n^m}{m!} \sim e^{m\ln n ...
5
votes
2answers
157 views

Find asymptotics of $x(n)$, if $n = x^{x!}$

Find the asymptotic for $x(n)$, if $n = x^{x!}$. I've tried 1) to take a logarithm: $x! \log{x} = \log{n}$. 2) to find $n'(x)$, using gamma-function for factorial $\Gamma(z) = \int_0^\infty ...