Tagged Questions

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

How to extract $O(h^2)$ from $f\left(t_{i+1},y_i+hf(t_i,y_i)+O(h^2)\right)$

This is the formula of explicit Heun's method $$ y_{i+1}=y_i+hf\left(t_{i+1},y_i+hf(t_i,y_i)+O(h^2)\right)+O(h^3) $$ and I want to prove that this formula is $O(h^3)$.
0
votes
0answers
26 views

Question about computing two asymptotics

Fix $k$. Is there a constant $c \in (0,1)$ such that if $L=cn$ and $n$ tends to infinity then $$\frac{(2k)!}{2^kk!}{2nL - L^2 \choose 2k} \sim \sum_{s=0}^k{L \choose s}{n-L \choose ...
0
votes
0answers
13 views

Asymptotics of two expressions

I'd like to know something about this equation $\frac{(2k)!}{2^kk!}{2nL - L^2 \choose 2k} = \sum_{s=0}^k{L \choose s}{n-L \choose s}s!\frac{(2k-2s)!}{2^{k-s}(k-s)!)}{L-s \choose 2k-2s}.$ I am ...
0
votes
2answers
33 views

Order of error of a fraction

If two functions can be written as the sum of some expression and an error term of higher orders of error $\epsilon$: $$f(x+\epsilon)=f_0(x,\epsilon)+O(\epsilon^m)\quad \text{ and} \quad ...
0
votes
0answers
37 views

What's the right way to write big-O?

I always write $\mathcal{O}(n)$ (\mathcal{O}(n)). But I frequently see $O(n)$ (O(n)), probably because it's shorter and more ...
1
vote
0answers
43 views

sum over primes involving divisor function (variation of the Titchmarsh divisor problem)

Does there exist an asymptotic estimate for the following sum over primes $$ \sum_{p\leq x} \frac{\tau(p-1)}{p}\;, $$ where $\tau(n)=\sum_{d|n}1$ is the divisor function?
1
vote
1answer
34 views

What is the result of $\frac{h^2}{2}O(h)+O(h^3)$

Why and how in the following expression $$ y_{n+1}=y_n+hy^{\prime}_n+\frac{1}{2}\left[ \frac{y^{\prime}_{n+1}-y^{\prime}_n}{h}+O(h) \right]h^2+O(h^3) $$ $$\Rightarrow y_{n+1}=y_n+h\left( ...
0
votes
1answer
24 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 ...
1
vote
2answers
33 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 ...
2
votes
0answers
18 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 ...
1
vote
2answers
41 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 ...
0
votes
1answer
14 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
24 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
28 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 ...
0
votes
1answer
32 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
0answers
42 views

Using Limits to Determine Big-O, Big-Omega, and Big-Theta

I am trying to get a concrete answer on using limits to determine if two functions, $f(n)$ and $g(n)$, are Big-$O$, Big-$\Omega$, or Big-$\Theta$. I have looked at my book, my lecture notes, and have ...
1
vote
3answers
67 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 ...
1
vote
1answer
53 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
28 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 ...
0
votes
0answers
45 views

How is $O(\log(\log(n)))$ also $O( \log n)$?

How is $O(\log(\log(n)))$ also $O( \log n)$? I have seen this result somewhere with this but I still didn't quite understand how this is true. This would also help me compute Big Omega of the ...
0
votes
1answer
69 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
36 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 ...
7
votes
0answers
132 views

Is it true that $\gamma_{\lfloor\log\Gamma(x)\rfloor}\sim 2\pi x$?

I realise that Gram points can approximate the imaginary part on the $x$th zeta zero $(\gamma_x)$ accurately, and indeed, Guilherme França, André LeClair give another formula, namely ...
1
vote
0answers
14 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 ...
4
votes
1answer
99 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 ...
0
votes
1answer
40 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, ...
0
votes
1answer
40 views

How to differentiate an expression involving big-o notation?

From Apostol - Introduction to analytic number theory (Theorem 3.3) we have $$ x\geq1, \sum_{n\leq x}d(n)=x\log x+(2\gamma-1)x+O(\sqrt{x}):=E(x), $$ I want to differentiate $E$ -- to get a rough ...
0
votes
1answer
55 views

Find Recurrence Relation of Code

Suppose A(n) be the number of stars that wrote with the following example. for n>=3, i want calculate the recurrence relation for this code. any idea or solution? ...
1
vote
1answer
44 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 ...
2
votes
2answers
85 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 ...
0
votes
1answer
35 views

Is f(n) = O(g(n)), Ө(g(n)), or Ω(g(n))?

I have f(n) = n − 100, and g(n) = n − 200. I'm supposed to figure out if f(n) = O(g(n)), Ө(g(n)), or Ω(g(n)). How can I go about that? I have the definitions of these asymptotic notations, but I do ...
4
votes
0answers
36 views

The Basic Example and Output of Algorithms [closed]

if exg(x,y) swap the x,y, and array A contains integer numbers, the following algorithm how modify the $A[1]$ and what is the operation of the following algorithm? i confused to trace this code. any ...
2
votes
1answer
34 views

Time Complexity of one Example Code

i see an example on my note for calculating Time Complexity, but i couldn't understand. anyone could help me.
-1
votes
1answer
56 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 ...
2
votes
1answer
25 views

Time Complexity of one Challenging Example

Anyone would help me to calculate the order (time complexity) of this example ?
4
votes
0answers
54 views

Increasing Growth Rate Challenge [closed]

why from left to right, we have increasing in growth rate? any description for some usual equivalence formula for each of them?
8
votes
2answers
153 views

Algorithm for adding n 1-bit numbers

suppose adding two numbers, (that first number has a bits and second number has b bits) can be done in ...
0
votes
0answers
20 views

Using singularity analysis to find the main asymptotic term of the Catalan Numbers

Using singularity analysis to find the main asymptotic term of the Catalan Numbers \begin{align} C_n = [z^n]\frac{1-\sqrt{1-4z}}{2z} \end{align} Can someone please explain to me the general concept ...
1
vote
1answer
22 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
44 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
27 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
39 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. ...
3
votes
3answers
260 views

Find a real entire function $f(z)$ asymptotic to $\ln(x^2+1)$ for real $x$.

Find a real entire function $f(z)$ asymptotic to $\ln(x^2 +1)$ for real $x$. More specific I want $f(0)=0$ and $\frac{1}{2} \ln(x^2+1) < f(x) < 2 \ln(x^2+1)$. Or prove it does not exist.
4
votes
1answer
62 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
45 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 ...
3
votes
1answer
31 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. ...
0
votes
1answer
78 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
34 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) ...
2
votes
1answer
54 views

Asymptotic expansion of an integral with exponential decay and highly oscillating kernel [closed]

I would appreciate if one can get the leading term of the following integral: $$I(x) = \large{\int}_0^\infty \frac{g(s)}{\sqrt{s^2 + \frac 1 4}}e^{- i x s- m x\sqrt{s^2 + \frac 1 4}}ds$$ as ...
1
vote
1answer
32 views

Do small o, small omega, and big theta cover all relationships between two functions

Given any two functions $f(n)$ and $g(n)$ is one of these three statements always true: $f(n) \in o(g(n))$ $f(n) \in \omega(g(n))$ $f(n) \in \Theta(g(n))$ Logically, this makes sense to me. For a ...