0
votes
2answers
31 views

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

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

prove that θ(n-1)+ θ(n)= θ(n)

I need to prove that statment with big Theta defenition.. θ(n-1)+ θ(n)= θ(n) I have tried many things but cant prove that with defenition of theta
-1
votes
1answer
36 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
20 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
13 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
55 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
24 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
36 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
34 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
22 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
35 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
81 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
59 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
68 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
56 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
75 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
48 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
74 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
42 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
75 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
30 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
87 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
32 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
30 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
34 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
43 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
28 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
34 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
131 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
95 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
42 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
74 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
51 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
106 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
154 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 ...
5
votes
1answer
117 views

Find asymptotic for $s(n)=\min\{m\in{\mathbb N}\mid C_n^m\cdot e^{-m^3/(\ln m)^{10}}<1\}$

I have some strange function: $s(n)=\min\{m\in {\mathbb N} \mid C_n^m\cdot e^{-m^3/(\ln m)^{10}}<1\}$ and I need to find asymptotics for it. I have a solution for this except one last step, I ...
0
votes
0answers
112 views

Solving recurrence using Master Theorem: Change of variables

Solve the recurrence using the Master Theorem State case and constant values used. $$T(n)=3T(\sqrt[3]{n})+log^2n$$ The $\sqrt n$ has a 3.(The number is a little small) I need to solve this using ...
0
votes
1answer
162 views

Prove that Big O (lg n) is a subset of Big O(sqrt(n))…

Prove that Big O (lg n) is a subset of Big O(sqrt(n)) and exists an element x in set Big O(sqrt(n)) that is not in Big O(lg n). This is a home work question and I have no clue where to start. Do I use ...
2
votes
4answers
427 views

Prove that $3^n$ is not $O(2^n)$

I have this question in my assignment. I need to prove, using only the definition of $O(\cdot)$, that $3^n$ is not $O(2^n)$. It is obviously true for any $n \geq 1$. To prove $3^n \in O(2^n)$, we ...
3
votes
1answer
58 views

Showing an approximation is uniformly asymptotic

I am trying to show that the approximation on $0\leq x \leq 1$ $$\phi(x,\epsilon) \sim \sin x+ \epsilon \cos x - \epsilon$$ is uniformly asymptotic to the exact solution $$f(x,\epsilon) = ...
7
votes
1answer
143 views

Approximate $\int_0^{\pi /2} \frac{ds}{\sqrt{1-x\sin^2s}}$

I am trying to approximate the following integral $$K(x)=\int\limits_0^{\pi /2} \frac{ds}{\sqrt{1-x\sin^2s}}$$ with $0<x<1$. I need to show that for x close to one that $K(x)\sim ...
-1
votes
1answer
35 views

Finding $k$, $C_1$, and $C_2$ when $f(x)$ is $Θ(g(x))$

How can I find the constants $k$, $C_1$, and $C_2$ when I know that $f(x)$ is $Θ(g(x))$? $f(x)=3x^2+x+1$ and $g(x)=3x^2$ I have that $C_1g(x) \le f(x) \le C_2g(x)$ $C_1 \le \frac{f(x)}{g(x)} \le ...
0
votes
1answer
366 views

Prove: $\theta(n^2)+O(n^3)\subset O(n^3)$

I believe that my understanding of this question is incorrect, so any help would be appreciated. The Question: Prove: $\theta(n^2)+O(n^3)\subset O(n^3)$ Note that for this problem, you are proving ...
2
votes
2answers
261 views

Using Master's Theorem with $f(n) = \lg^2 (n)$

This is a homework question about using Master's theorem, and I can't seem to wrap my head around this question: $$T(n)=2T\left(\frac{n}{3}\right)+\lg^2(n)$$ I've tried to apply the Master's ...
0
votes
2answers
670 views

Proof of $\Theta (n^2) + O(n^3) \ne O(n^3)$

This is a homework question. I have proved before that the sum of the terms on the left-hand-side are a subset of $O(n^3)$, but I have not proved that the two terms are not equal (or whether that was ...