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
1answer
32 views

What are basic methodologies on solving questions related to comparison of rate of growth of two different functions?

How to compare rate of growth for following functions? In other words, is $f(n)$ = $O( \, g(n) \, )$ or $g(n)$ = $O(\, f(n) \, )$? $f(n) = n^{\frac{4}{3}}$ and $g(n) = n*(\log(n))^3$ How to solve ...
0
votes
1answer
293 views

Asymptotic distribution of MLE of geometric distribution

I need to find the asymptotic distribution of the MLE of a geometric distribution. I know $\overline X$ goes as $N(1/p, (1-p)/(n p^2))$. Using the delta method MLE=$1/\overline X$ goes as $N(p, ...
1
vote
2answers
49 views

O-notation: composing functions

Big-oh and little-oh notation make things much simpler, and there are convenient rules for combining functions, for example, the ones mentioned here. One rule conspicuously missing from the above ...
1
vote
2answers
92 views

Series expansion of incomplete gamma function ratio

I am interested in the series expansion of: $$S(k)=\frac{\Gamma(k+1,a)}{k!},$$ around $k=\infty$ where $\Gamma(x,z)$ is the incomplete gamma function and $a$ is some positive constant. In ...
1
vote
3answers
71 views

Is $(n^{1/n}-1)\in O(n^{-\frac12})$ as $n\to \infty$?

Let $$x_n=n^{1/n}-1$$ An exercise asks me to prove that $\{x_n\}\to 0$ and that $x_n\in O(n^{-\frac12})$ as $n\to \infty$. Now, I could easily prove the first part. But to me $x_n\notin ...
2
votes
0answers
150 views

Comparing asymptotic growth of logarithmic functions by reasoning

As an exercise, we're sorting functions according to their asymptotical growth. When comparing these two functions, I'm getting stuck: $n^2/(\log_2 n)^3$ versus $n \log_2 n$. Using limits I am ...
0
votes
1answer
39 views

Finding family of curve for given asymptotes

I need to find possible curves, with asymptotes given as $x=0 (x \to -\infty)$ and $y=mx \hspace{0.5cm} m>0$. it is easy to find curves for individual lines, $y= \exp(-\lambda_1 x) + mx$ for $y=mx$ ...
1
vote
1answer
63 views

How can I construct a specific sigmoid function?

The simple sigmoid function $$f(x)=1/(1+e^{−x})$$ approaches zero as x tends to negative infinity, and approaches $1$ as x tends to positive infinity. But I want to set $1$ and $20$ instead of $0$ and ...
1
vote
2answers
61 views

How can I find The Big Oh bounds for a summation with multiple variables?

I have this as a homework problem so I won't post the same thing. I'll just post what I need to know to move forward. $$ \sum_{i=0}^n 10^i i^2 $$ I'd just like to know how to split this ...
8
votes
2answers
5k views

Value of Summation of $\log(n)$

Context: I am learning Dijstra's Algorithm to find shortest path to any node, given the start node. Here, we can use Fibonnacci Heap as Priority Queue. Following is few lines of algorithm: ...
0
votes
1answer
50 views

What is $\ O\left({n\over \left(\log \log n\right)^2}\right) $ equal or approximately equal to?

I already know big O notation and its use, but I can understand neither its value (or its approximation) in a "normal, ordinary" form (I'm referring to stuff like $\ n^2, 2n+1, 2^n $ etc.), nor ...
1
vote
1answer
62 views

$\sin(x)$ is asymptotically equal to $x+5x^3$

Here is my question: I've never seen before this kind of fact underlined about asymptotic equalities (and why we keep only one term in these equalities) and I'm looking for reference. Here is an ...
1
vote
1answer
43 views

Parabolic asymptote of $n\cot\frac\pi{2n}$

I have determined that $$\lim_{n\to\infty}\frac{n\cot\frac\pi{2n}}{n^2}=\lim_{n\to0^+}n\cot{\frac{\pi n}2}=\lim_{n\to0^+}\frac{n\cos{\frac{\pi n}2}}{\sin{\frac{\pi n}2}}=\frac2\pi$$ So that the ...
1
vote
1answer
214 views

The solution of recurrence $T(n) = 2T(\lfloor{n/2}\rfloor + 17) + n$ is $O(n\lg n)$

Given, $T(n) = 2T(\lfloor{n/2}\rfloor + 17) + n$. Show that the solution to T(n) is $O(n\lg(n))$. Here's what I tried - Assumption: $T(\lfloor n/2 \rfloor) \le c(\lfloor n/2\rfloor + 17)\cdot ...
2
votes
0answers
61 views

Find an asymptotic upper bound

Use the substistution method to find an asymptotic upper bound for the relation $$T(n)=3 T\left ( \frac{n}{3}+5 \right )+\frac{n}{2}$$ Try so that the bound is as accurate as possible. Consider that ...
3
votes
2answers
126 views

Is there a closed form for $\sum_{j=1}^{n} j^2\log{j}$?

Question Is there a closed form for $\sum_{j=1}^{n} j^2\log{j} = 1\times0 + 2^2\times\log{2} + 3^2\log{3} + \dots + n^2\log{n}$? I'm trying to look for the simplest $\Theta$ notation. Attempt Let ...
1
vote
0answers
33 views

Recursive relation-Theta notation

Consider the recursive relation: $$T(n)=T(an)+T((1-a)n)+cn$$ where $0<a<1$ and $c>0$ are constants(independent of $n$).Show that $T(n)=\Theta(n \lg n)$ That's what I have tried: We ...
0
votes
1answer
38 views

Need an Algorithm Such that $\sum_{k-i}^{j}{A[k]}$

I need an algorithm for real application. Suppose we have array A (positive & negative ) numbers. we want to find index i, j such that $\sum_{k-i}^{j}{A[k]}$ has the lowest difference to zero. ...
4
votes
1answer
109 views

Expected time to get from bottom left to top right in a square

Consider a two dimensional random walk starting at the bottom left hand corner of an $n$ by $n$ square. At each step you take one step up, down, left or right distance $1$. Each choice has equal and ...
1
vote
1answer
63 views

Asymptotic behavior of the solution to an equation

Let $c\in(0,1)$ be a constant and let $k$ be a positive odd integer, and let $a(k)$ denote the value of $a$ that satisfies the equation $$(1-a)^kk\sqrt{a}=c$$. As $k\rightarrow\infty$, what can we ...
1
vote
1answer
109 views

Is 1/x the “slowest” asymptotically falling off differentiable function?

As a physicist, I tend to think about $\sim 1/x$ as the "slowest" fall-off of a "reasonable" function. Let us state this formally: $${\rm lim}_{x \to \infty} f(x) = 0, f(x) \in Reas \implies \exists A ...
0
votes
1answer
184 views

The order of convergence and the asymptotic error constant of the sequence $p_n=g(p_{n-1})$

Let $g(x)=0.5(x+a/x)$. Determine the order of convergence and the asymptotic error constant of the sequence $p_n=g(p_{n-1})$ toward $x=a^{.5}$. This is a problem in our homework in the class ...
4
votes
1answer
103 views

Asymptotics on the largest prime for which $x^n+1\equiv y^n$ has no nonzero solution

It $\let\epsilon\varepsilon\let\leq\leqslant\let\geq\geqslant$is a well known result that for every $n\in\mathbb N$, $x^n+1\equiv y^n\pmod p$ is non-trivially solvable for sufficiently large primes ...
1
vote
1answer
27 views

Find a power series expansion of $\frac{4x^2+2x}{1-3x-10x^2}$ about the point $x = \frac{1}{5}$

Find a power series expansion of $\frac{4x^2+2x}{1-3x-10x^2}$ Now I know that $\frac{1}{5}$ is a singularity of the $\frac{4x^2+2x}{1-3x-10x^2}$ and I know that $f(z) = ...
0
votes
1answer
99 views

Which case of the Master theorem applies to the recurrence $T(n)= 100T(n/99)+\log(n!)$?

How to use the Master theorem to solve $T(n)= 100T(n/99)+\log(n!)$? I was given this question, and I can't figure out which case of the master theorem goes here. Thanks for your suggestions.
0
votes
1answer
43 views

Lower Bound Omega Notation

I have to prove that some number $S$ is bigger than $\Omega(|V|)$, where |V| is the number of vertices. I read the definition of asimptotic notations, but I am still confused with the examples. Fot ...
1
vote
1answer
90 views

Question about efficiency of an algorithm (Big-O)

The efficiency of the algorithm dolt can be expressed as O(n)=n^3.Calculate the efficiency of the following program segment exactly and by using the big-O notation. ...
-2
votes
1answer
410 views

Every uniformly continuous real function has at most linear growth at infinity

Assuming $f:\mathbb R\to\mathbb R $ be an uniform continuous function, how to prove $$\exists a,b\in \mathbb R^+ \quad \text{such that}\quad |f(x)|\le a|x|+b.$$
1
vote
1answer
66 views

Closed form for estimated sum with different asymptotic bounds?

I found asymptotic lower and upper bounds for a summation as follows: $$ 1 - O\left(\frac{\log_2^2 n}{n}\right) \le \sum_n f(n) \le 1 + O\left(\frac{1}{n}\right).$$ If you want to write it in a ...
4
votes
1answer
99 views

Details from a Proof that a Tournament has Property $S_k$

(Edit: While the context is not central to my question, I decided to include it anyway to make the question a little more searchable.) Some technical details are omitted from a theorem in Alon and ...
0
votes
1answer
98 views

What are sets and classes in maths, and how are they related to $O()$ and $o()$ notation?

Are there many definitions of sets and classes in mathematics, as given in Formal definion of the notations used in measuring time complexity? And in particular, why the notation given in Fedja's ...
0
votes
0answers
52 views

Big O evaluations

I'm confused about how to approach Big O problems. I'm presented two functions: $$f(n) = 4^{log_4n}$$ and $$g(n) = 2n +1$$ I simplified f(n) to: $$f(n) = n$$ Now I'm not sure how to compare f(n) ...
0
votes
1answer
53 views

Omega Notation and Average Running Time Problem

if we have an algorithm that average running time of randomized algorithm A for input of size n is equal to $\theta(n^2)$. why there would be an input data such that A solve it in $\Omega(n^{3n})$?
0
votes
1answer
22 views

How do you solve a recurrence with a functin through induction?

I found the answer in part-A by substitution, as O(n) from; T(n/2^k) = T(1).... n/2^k = 1..... so k = 1og2(n)..... T(log2(n)) = T(n/n)+5.... so O(n) IS THE ANSWER, Correct me if am wrong because am ...
5
votes
0answers
134 views

Boundary Layer, leading order, Pertubation Theory, Differential Equations

I have got the following problem, taken from Multiple Scale and singular perturbation methods, Kevorkian & Cole book, page 94, exercise 1.b.: Find the leading order of the problem: $\varepsilon ...
0
votes
0answers
336 views

Taylor series expansion and Laplace transform final value theorem

I cant figure out how some transformations are made in one article on physics. Here is expression in s-domain and they want to find its asymptotic value. $$ \xi(s) = \nu_1(s+1)=\frac{1}{(s+1)} ...
0
votes
1answer
52 views

Confusion with Big-oh

So, big-oh means: for at least one choice of a constant k > 0, you can find a constant a such that the inequality f(x) < k g(x) holds for all x > a So let's evaluate the statement $1 = ...
2
votes
0answers
58 views

Density of Pythagorean triples

We define a Pythagorean triple as a triple $<a,b,c>$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$. In order to avoid duplicates, we say that a triple $<a,b,c>$ is legit iff $b>a$. ...
1
vote
3answers
265 views

Big-O, Omega, Theta and Orders of common functions

Based on this table, is it generally going to be true that for two functions whose most "significant" terms are of the same order that they will be big-Theta each other? And a function of order ...
1
vote
1answer
64 views

How to rigorously simplify an expression with Big-Oh Composed within another Big-Oh.

I am trying to show the following: $$ O(e^{n(\cos n^{-2/5}-1)}) = O(e^{-Cn^{1/5}})$$ The problem I'm having is I'm trying to get a hang of asymptotic notation, and I can't quite figure out how to ...
1
vote
0answers
108 views

Find a closed form for the constant term

In a previous question, an asymptotic expansion was provided for the weighted divisor summatory function $\displaystyle \frac {d(n)}{n}$: $$\sum_{n\leq ...
8
votes
4answers
626 views

The asymptotic expansion for the weighted sum of divisors $\sum_{n\leq x} \frac{d(n)}{n}$

I am trying to solve a problem about the divisor function. Let us call $d(n)$ the classical divisor function, i.e. $d(n)=\sum_{d|n}$ is the number of divisors of the integer $n$. It is well known that ...
1
vote
0answers
20 views

Showing that $\prod_i{\frac{qi-1}{qi}}=\exp(-\frac{\log n- \log q +O(1)}{q})$

I'm currently making my way through Dixon's paper 'The Probability of Generating the Symmetric Group'. (It can be found here.) In the proof of lemma 3 it is asserted that ...
1
vote
1answer
44 views

Proving that $ \frac{1}{n}\int_{-\infty}^{\sqrt{n}w}k(v/\sqrt{n})\phi(v)dv$ is $O(n^{-1})$

Suppose that $h:\mathbb{R}\to\mathbb{R}$ is infinitely differentiable. Define \begin{equation} k(w)=\left\{ \begin{array}{ll} \frac{d}{dw}\left(\frac{h(w)-h(0)}{w}\right)&w\neq 0,\\ ...
1
vote
1answer
80 views

Switching Limits and summation

I'm currently working on proving some theorems and there is one recurring problem that I somehow can't solve. $a_n$ is a real sequence in either $[0,1]$ or $\mathbb{R}$ that approaches $0$. ...
1
vote
1answer
58 views

Asymptotics of logarithm: $\frac{1}{n}\ln(a+o(1)) = \frac{1}{n}\ln(a)+o(\frac{1}{n})$

I am having problems with the use of the little oh notation my professor is adopting in the solutions to some exercises. As an example I do not understand why $$ \frac{1}{n}\ln(a+o(1)) = ...
1
vote
1answer
34 views

Lower bound on $F$ under the assumption $\theta F(s)\le sF'(s)$

Let $F(s)=\displaystyle \int_0^{s}f(t)\,\mathrm dt$. We suppose that there exists $\theta>2$ such that $\theta F(s)\le f(s)s$ for all $s\in \mathbb{R}$ and that $F(s)>0$ for all ...
0
votes
1answer
426 views

What's time complexity of algorithm for “Word Break”?

Word Break(Dynamic Programming) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible ...
9
votes
3answers
138 views

Prove that $\prod_{k=1}^{\infty} \big\{(1+\frac1{k})^{k+\frac1{2}}\big/e\big\} = \dfrac{e}{\sqrt{2\pi}}$

This result, $$\prod_{k=1}^{\infty} \big\{\big(1+\frac1{k}\big)^{k+\frac1{2}}\big/e\big\} = \dfrac{e}{\sqrt{2\pi}}$$ is in a paper by Hirschhorn in the current issue of the Fibonacci Quarterly (vol. ...
1
vote
0answers
39 views

Asymptotic behaviour / Convergence

Let $0<\omega<\infty, \mu >0$ and $z \in \mathbb{R}.$ In my book, it is written that we have the following asymptotic behaviour: i) Claim: $$\lim_{t \rightarrow \infty} \frac{z ...