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

learn more… | top users | synonyms (1)

3
votes
0answers
77 views

Which series of numbers effectively translates the factorial to the exponential function?

We have the relation of the Bernoulli numbers $$B_{2n} = (-1)^{n+1}\frac {2(2n)!} {(2\pi)^{2n}} \left(1+\frac{1}{2^{2n}}+\frac{1}{3^{2n}}+\cdots\;\right).$$ For $n>1$, the right hand sum ...
0
votes
1answer
270 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
124 views

How to determine growth rate of coefficients of generating function

For a given ordinary generating function $f(x)=a_0+a_1x+...$, are there any methods to determine the growth rate of its coefficients based on that of $f$ ? In particular if we are given the extra ...
1
vote
1answer
90 views

Asymptotes of $\Gamma(\frac{1}{2} +ix)$ when $\vert x \vert \to \infty$

I am currently looking for finding behaviour of the function $\vert \Gamma(\frac{1}{2}+ix) \vert$ when $x$ tends to $\infty$. I think I need to use the Stirling's approximation but I don't see how. ...
0
votes
1answer
21 views

BigOh - How to determine the upper bound dealing with eccentric series?

I would like to know what is the way to determine the upper bound of a series in BigOh terms. For example, suppose the following series is given: 2 + 6 + 10 + 14 + ..... + ((4 * n) - 2) How can I ...
1
vote
1answer
437 views

Asymptote of a parametric equation (with Arctan)

I need to find the asymptotes of a parametric equation. My book says you have a vertical asymptote when $y\to \infty$. But the parametric equation is the following: $$x= \frac 13t^3-\pi,y= \frac ...
3
votes
2answers
74 views

Asymptotic expansion of $\sum_{k=0}^{\infty} k^{1 - \lambda}(1 - \epsilon)^{k-1}$

I'm seeing a physics paper about percolation (http://arxiv.org/abs/cond-mat/0202259). In the paper the following asymptotic relation is used without derivation. $$ \sum_{k=0}^{\infty} k P(k) (1 - ...
1
vote
1answer
444 views

Solving the recurrence $T (n) = \sqrt{n} T(\sqrt{n}) + O (n)$ [duplicate]

I want to show that the requrrence $T (n) = \sqrt{n} T(\sqrt{n}) + O (n)$ is in $O(n \log \log n)$ Here's my attempt: If we expand the recursion tree, at a level $i$, there are $n^{1/2^k}$ ...
4
votes
1answer
64 views

asymptotics of inverse function

Suppose $f:[0,\infty)\to [0,\infty)$ is strictly increasing with $f(0)=0$ and it's given explicitly as a combination of elementary functions. How do you find the asymptotics of $f^{-1}(x)$ as $x\to 0$ ...
1
vote
2answers
133 views

How does big-O notation relate to the actual error involved in a numerical differentiation?

Suppose I have some position data ${x_1, x_2, ... x_n}$ that was sampled at an interval $h$. If I wanted the velocity data, I could apply a finite difference scheme: $ v_1 = \frac{x_2 - x_1}{h} + ...
4
votes
0answers
91 views

Prove that a series is $O(t^a)$.

Consider the series $$ u(t,x) = \sum_{i \geq 1} {u_i(x) t_1^i } + \sum_{i+2j \geq k+2, j\geq 1} {\varphi_{i,j,k}(x) t_1^i t_2^j y^k} $$ where $t \in \tilde{\mathbb{C} \setminus \{ 0 \}}$, $x$ is ...
2
votes
0answers
36 views

Asymptoticity of a definite integral

friends! I read on a book that, for $\alpha>1$, "being $g$ continuous in 0 [really $g$ is continuous in $[0,1]$, if it were useful to know] and approaching the extremes of the integral 0 for $n\to ...
0
votes
1answer
40 views

Ordering Equations Using Small-oh Notation.

I have a couple questions about this problem: Order the following functions $h_i$, for $1 \leq i \leq 5$, with respect to relation $f \prec g$ defined by the small-oh notation as follows: $f \prec ...
0
votes
1answer
95 views

Derive Time from Sorting Method/Time Complexity

A sorting method with “Big-Oh” complexity O(n log n) spends exactly 1 millisecond to sort 1,000 data items. Assuming that time T(n) of sorting n items is directly proportional to n log n, that ...
4
votes
0answers
65 views

prime zeta function when $0<s<1$ [duplicate]

I would like to know if there is a good estimate for the sum which concerns all primes not exceeding $x$: $$\sum\limits_{p\leq x}\frac{1}{p^s}$$$$0<s<1$$. Only this. Thanks in advance!
-1
votes
1answer
41 views

Big O Notation for a constant running time

I came across a question asking the following: Why is the O-notation for a constant running time always given as O(1)? I have been thinking about it but I can't make sense of it. Could anyone ...
2
votes
2answers
92 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
3answers
2k views

Prove Upper Bound (Big O) for Fibonacci's Sequence?

NOTE: We are not to use proofs (limits, induction, or otherwise) in this problem. We were to prove the upper bound for the Fibonacci recursion is some exponential. The Fibonacci recurrence relation ...
0
votes
2answers
141 views

The result of O(f(n)) - O(f(n))

My question is in the field of the big-O-notation and complexity/asymptotic functions: Probably something that I'm missing, but I've couldn't find any well explained solution for the following: What ...
1
vote
1answer
121 views

Help with Recursive Algorithm

We are to determine a recurrence relation for a recursive algorithm. Let us use the Josephus Problem for this: Given n people standing in a circle, every kth person is killed until one person ...
1
vote
1answer
67 views

Asymptotic expansion for calculating exact value

I have shown that $F(x)=\int_0^\infty\frac{e^{-t}}{(1+xt)^2}dt\sim\sum_{n=0}^\infty (-1)^n (n+1)! x^n$ as $x\rightarrow 0_+$. My question now is that when we are given a small value $x$ how can I ...
2
votes
1answer
90 views

Behaviour of $\int_0^{\frac{\pi^2}{4}}\exp(x\cos(\sqrt{t}))dt$

I want to analyze the behaviour of $\int_0^{\frac{\pi^2}{4}}\exp(x\cos(\sqrt{t}))dt$, i.e I want to show it behaves like $e^x(\frac{2}{x}+\frac{2}{3x^2}+...)$ as $x\rightarrow \infty$ I started by ...
5
votes
1answer
131 views

Integral asymptotic expansion of $\int_0^{\pi/2} \exp(-xt^3\cos t)dt$ as $x \to \infty$

I have the integral $$I(x)=\int_0^{\pi/2}\exp(-xt^3\cos t)dt$$ and I want to derive the first two terms in the asymptotic expansion for $x\rightarrow \infty$, which should give me ...
1
vote
2answers
392 views

List of calculation rules for asymptotic notation?

Background: I am working my way through CLR/CLRS's proof of the master theorem (section 4.4 in the 1st and 2nd editions of Introduction to Algorithms), and I'm doing my own write-up of this proof1 ...
1
vote
1answer
38 views

A problem about power series and big-O

The problem is: Prove: There exist constants $a$, $b$ such that $\frac{z^3-5z^2+3z}{(z+2)^3}=1+\frac{a}{z}+\frac{b}{z^2}+O(\frac{1}{z^3})$ as $z\rightarrow \infty$ and find an explicit values for $a$ ...
0
votes
0answers
31 views

Little O Bound, Combinatorics

I am reading a book on combinatorics. I tried deriving the result in the following sentence, but could not get it. Can someone show me the algebra? Theorem 1.2.1: If $\dbinom{n}{k} {(1- ...
2
votes
1answer
96 views

Showing $\sum_{n\in\mathbb{N}}\frac{\Lambda(n)}{n}=\log (x)+O(1)$ using a given result.

I'm stuck on the following problem. Use the fact that $$\sum_{p\le x}_{p\,\text{prime}}\frac{\log p}{p}=\log (x)+O(1)$$ to show that $$\sum_{n\le x}_{n\in\mathbb{N}}\frac{\Lambda(n)}{n}=\log ...
1
vote
0answers
43 views

How does one prove that $n^{-100} = \omega(2^{\sqrt{\log{n}}})$?

I feel that $2^{\sqrt{\log{n}}}$ could be dramatically simplified, but I'm sure how. Aside from plugging in huge values to test the functions, any ideas on how I can prove this relationship?
2
votes
1answer
34 views

How do I prove that a constant $C$ exists that matches these bounds?

For $n \in \mathbb{Z}^+$, given any function $T(n)$ such that $T(n) = \Omega(n^3)$ and $T(n) = O(n^4)$, how can I prove that constants $C$ and $N$ exist such that $$ n^3 + 10 \le CT(n) \le n^4 $$ ...
0
votes
1answer
60 views

$d>0$ Prove $ d^n =O(n!)$

To solve this question , I came up below kinda solution: $ d^n $ $\leq n!$ $\frac{d^n}{n!} \leq$ constant But how am I prove this. By the way this is Big Oh Notation
0
votes
2answers
240 views

Find and Prove $\sin(n)=O(g(n))$ [closed]

prove $g(n)$ such that $\sin(n)=O(g(n))$. I need to prove how the behavior of function sin(n)?
2
votes
1answer
89 views

Big O proof of Fourier Coefficient

Let $f(x)$ be a $2\pi$ periodic function on R. Assume that Hölder continuous: $$\sup_{x\neq y} \frac{|f(x)-f(y)|}{|x-y|^{-\alpha}} \leq C$$ for some constants $C$ and $\alpha \in \,]0,1]$. Prove ...
0
votes
1answer
139 views

Big-Oh, Big-Omega, Big-Theta

Can someone provide concrete reasoning for how to solve the following equations with respect to Big-Oh, Big-Omega, and Big-Theta? \begin{equation} 6n^2 + 20n = O(n^3) \end{equation} \begin{equation} ...
2
votes
0answers
39 views

Farey Sequences and how evenly is the sequence distributed

Given any $\alpha,\beta\in (0, 1)$, $k\in Z^+, n > 1$ is this true ($\mathcal{F}_n$ denotes the $n$th Farey sequence, and $\mathcal{F_n}^{\prime} = \{q:q = a + b, a\in\mathbb{Z}, ...
2
votes
3answers
225 views

Equation with the big O notation

How I can prove equality below? $$ \frac{1}{1 + O(n^{-1})} = 1 + O({n^{-1}}), $$ where $n \in \mathbb{N}$ and we are considering situation when $n \to \infty$. It is clearly that it is true. But I ...
0
votes
3answers
44 views

Show that $\log_{10}(x^2 + 1)$ and $\log_2 x$ have the same order of growth [closed]

How do I show that that $\log_{10}(x^2 + 1)$ and $\log_2 x$ have the same order of growth? I don't how to simplify it for both of them to appear to have the same max polynomial equivalent. Any help ...
1
vote
1answer
78 views

Calculating algorithmic complexity

Given the following bit of code, how would I calculate the complexity? ...
1
vote
1answer
359 views

Time Complexity for $T(n) = T(\sqrt{n}) + 1$ [duplicate]

$$T(n) = T(\sqrt{n}) + 1$$ I am trying to find the time complexity of the given equation. I tried everything that I know but I could not find the answer. What I've tried: $k = lg(n)$ and $n=2^k$ -> ...
3
votes
1answer
158 views

Explanation for Terry T. post

I read here that : " If one inserts these inequalities into the Legendre sieve and optimises the parameter, one can improve the upper bound for the number of primes in $[N,2N]$ to $$O \left(\frac{N ...
1
vote
3answers
2k views

Big O notation - Proving that a function is not O(n)

Show that the function, $T(n) = 4n^2$ is NOT $O(n)$. I'm not looking for someone to give me a full answer, I just need some pointers on how to go about starting to show that it is not $O(n)$. Many ...
1
vote
3answers
101 views

Time Complexity in $\theta$ Notation

$$T(n) = 2T\left(\frac{n}{2}\right) + T\left(\frac{n}{4}\right) + 5$$ What is the time complexity of the given algorithm in $\theta$ notation. Thanks in advance.
1
vote
0answers
36 views

Frechet differentiability, asymptotic normality

I try to prove the asymptotic normality from the Frechet differentiability. Consider $$T(G)-T(F)=L_{F}(G-F)+o\left(d_{\star}(G,F)\right)$$ and ...
0
votes
1answer
39 views

Proving if equation is $O(\log n)$

How do I prove if \begin{equation} 2\log(n^{2}\log n) = O(\log n) \end{equation} is true? I began by trying to find a $C$ where \begin{equation} 2\log(n^{2}\log n) < O(\log n) \end{equation} ...
0
votes
2answers
110 views

Why isn't $\log(n!) \leq O(n\log n)$? [closed]

Why isn't $\log(n!) \leq O(n\log n)$? I know that $\log(n!)$ is of $\Theta(n\log n)$ but why can't a function that is of $\Theta$ be $\leq$ than a function that is $O$ of the same parameter? Isn't ...
1
vote
1answer
286 views

Proving functions to be Big Oh

How do I determine if there exists a function $f$, such that \begin{equation} f(n) = {\mathcal O}(\log n), \end{equation} but \begin{equation} 2^{f(n)} ≠ {\mathcal O}(n). \end{equation} Is ...
0
votes
1answer
115 views

Use algebra of Big-O notation to express tan($z$)

We can use the definition of Big-O notation to simply prove that $\sin(z)=z-\frac{z^3}{6}+O(z^5)$ as $z\rightarrow 0$, $\cos(z)=1-\frac{z^2}{2}+O(z^4)$ as $z\rightarrow 0$ and ...
2
votes
2answers
89 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
votes
1answer
114 views

Proving Big O(1) [closed]

How do I determine if the below is true or false? \begin{equation} 17^{100} + \frac{1}{n} = O(1)? \end{equation} I have tried using the c and No method but still can not come up with a solution.
0
votes
0answers
47 views

Proving big-O asymptotics for inverted matrices

Suppose $A,B:\mathbb{C}\rightarrow\mathbb{C}^{n\times n}$ are non-constant and invertible as matrices everywhere, and satisfy that $B$ is an entire holomorphic mapping and $A(z)=B(z)+O(1/z)$ as ...
0
votes
1answer
61 views

Proving Big Θ of summations with exponentials

I have been working on this problem but have had a hard time understanding how to prove it as True, which I believe it is. ...