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

Why can any values of C and N be chosen for the proof of Big-Oh?

In my CS course, they have taught us that, when proving Big-Oh, you can choose any positive integers to be C and k, following the definition. Based on that, they have taught us two different ways of ...
1
vote
1answer
23 views

Asymptotic behaviour of sequences

Could anyone explain in details how these approximations as $n \to \infty$ are found? ($a$ is a positive real number) ${x_n} = \frac{1}{n}\left( {\frac{a}{3} - \frac{3}{2}} \right) + O\left( ...
3
votes
0answers
34 views

Help understanding the complexity of my algorithm (summation)

As an exercise, I wrote an algorithm for summing the all elements in an array that are less than i. Given input array A, it produces output array B, whereby B[i] = sum of all elements in A that are ...
1
vote
1answer
13 views

Asymptotic stopping time for a ball-drawing problem

Take two different boxes, one with $N$ red balls and one with $N$ blue balls. Remove balls one at a time from either box with equal probability. When only one color is left, the (expected value of ...
0
votes
0answers
13 views

Limit of an indeterminated form?

I want to find: $$\lim_{t\to\infty}X_{t}$$ where: $$X_{t} = \frac{A_{t}^{a}}{B_{t}}$$ I know that: $$\lim_{t\to\infty}A_{t}=0$$ and $$\lim_{t\to\infty}B_{t}=0$$ Can I say with certainty that: ...
1
vote
1answer
23 views

Approximation of a generlized hypergeometric function for large parameters

I am looking for an approximation of a generalized hypergeometric function of the type $\, _0F_4$. I've stumbled upon the following approximation : assuming that none of a1,a2,…,ap is a nonpositive ...
-1
votes
0answers
25 views

Explain why a multiplying algorithm cant take less than O(n^2) time? [on hold]

Explain how best case analysis is fundamentally different in kind from worst case and average case analyses. Use a best case argument to explain why no algorithm for multiplying pairs of nxn matrices ...
0
votes
0answers
15 views

Doubt on asymptotics of continous functions (little-o notation and taylor expansion).

Suppose I have $e^{(\frac{1}{n}b + o(\frac{1}{n}))}$ then $\lim_{n \rightarrow \infty} = e^0 = 1$ so $$e^{(\frac{1}{n}b + o(\frac{1}{n}))} = o(1) +1$$ But if I take the Taylor expansion of ...
0
votes
0answers
13 views

Solution for asymptotic parametric equation

Say I have the following equation: \begin{equation} f(x) = A(t)^{c}g(x)h(x) \end{equation} where $\lim_{t\rightarrow \infty} A(t) = \infty$. Very importantly, $x \in [0,1]$. I want to find the ...
-1
votes
1answer
25 views

Approximation for the Summation of Sequence of Powers of Sines Functions. [on hold]

Let $z_1,z_2,...,z_m$ be real numbers such that $0<z_1,z_2,\ldots,z_m<\pi/2$, $z_1>z_2>...>z_m$ and $n$ an integer such that $n>0$. Prove that: ...
2
votes
0answers
33 views

Question related to the ballistic motion

A point mass will move in the gravitational field of the Earth according to the equation $$\ddot R =-\frac{GM_eR}{|R|^3},$$ where $R$ is the position vector of the point mass measured from the ...
2
votes
0answers
31 views

Asymptotic expansion of root of $\epsilon x \tan(x)=1$

Indicate a range of roots of $\epsilon x \tan(x)=1$ for which it is impossible to get an approximation using expansions. Since $\epsilon$ is small, I think for the equation to hold, we need ...
1
vote
2answers
37 views

A further question on asymptotic expansions of all real roots of xtan(x)=ϵ

I have asked a related question here How to find asymptotic expansions of all real roots of $x \tan(x)=\epsilon?$, however, when I discussed with my adviser today, he argued the solution is flawed. ...
0
votes
0answers
9 views

The size of the vertex hull of a lattice

Let $L$ be a lattice defined by $d$ vectors in $\mathbb{R}^d$. The Vertex Hull of a node $a$ at radius $r$ (denoted $VH(a, r)$) is defined to be the set of vertices that define the convex hull of $L ...
0
votes
4answers
75 views

Does $\lim \frac{a_n}{e^{\delta n}}=0$ for every positive $\delta$ imply that $\lim \frac{a_n}{\sum\limits_{k=1}^n a_k} =0$

Let's say we have an increasing sequence $a_n$ such that $\underset{n\rightarrow\infty}{\lim} a_n=\infty$. Now it's fairly clear to me, though I haven't proven this yet, that: ...
2
votes
1answer
19 views

Multiplying two matrices using Strassen vs squaring identical matrices

I have an assignment question such as follows: when using the Strassen algorithm we have 7 subproblems usually, and I suppose this applies to any two $n*n$ matrices and the run time is ...
2
votes
1answer
43 views

Asymptotic expansion of integral $F_m=2 \int_m^ \infty p(x)dx$.

$$p(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}$$ is the probability density function of the standard normal random variable. m-sigma quality control means that the probability of failure is less ...
0
votes
1answer
17 views

Difference between a convergent series and an asymptotic series?

Can someone let me know the difference between a convergent series and an asymptotic series with an example? Can both the series be the same at some situations? In what situations an asymptotic series ...
2
votes
2answers
64 views

How to find asymptotic expansions of all real roots of $x \tan(x)/\epsilon=1?$

Find expansions of all the real roots of $$x\tan(x)=\epsilon?$$ (You have to consider the first root separately) It is really bothering me. If I assume $x=x_0+x_1\epsilon +x_2\epsilon^2$ and do ...
3
votes
0answers
72 views
+50

Asymptotic behavior a recursion involving min/max

Usually when I face solving recursions I use generating functions but I'm not aware of any "tools" to use when min/max expressions are involved. For example, I have the following recursive term: ...
0
votes
0answers
38 views
+50

CDF of sum of 3 independent discrete uniform random variables on {1,2,…,n}

What is an approximate closed formula for this probability, with a derivation: p(k,n) is the probability, that among $n$ PC discs and $k$ errors in sum on them, there will be at least $1$ disc ...
0
votes
0answers
10 views

Asymptotic complexities of a conditional function

Let the function $f(n)$ be defined by $$f(n) = \dfrac{n^2}{7}$$, for n even and $$f(n) = 452n$$, for n odd I'm being asked to determine which statements are true and to show validation for those ...
2
votes
0answers
24 views

Asymptotic analysis of coefficients of ordinary generating functions with radius of convergence $1$ seems to always predict polynomial growth rate

Wikipedia gives the following formula for obtaining asymptotic information about the coefficients of an ordinary generating function from information about the generating function itself: if the ...
-1
votes
0answers
44 views

What is the slow manifolds? and how to calculate?

I'm a newbie in slow manifolds and dynamical system. I cannot understand the concept of slow manifolds and how to calculate that. Please explain the concept of slow manifolds intuitively and ...
0
votes
0answers
14 views

behavior of function

Im looking at the asymptotic behavior of the function $f(x)=x-c(\lceil \frac{x}{c} \rceil)$ as $x \rightarrow \infty$ for some constant $c>0$. I believe this function is bounded above by $0$ ...
1
vote
2answers
52 views

Notation issue - Asymptotic behaviour: is $\sim$ too restrictive?

As a student I am completely unable to understand unambiguously what is meant by a notation such as $$f \sim g $$ when in Physics the behaviour of two functions at infinity is evaluated. I found a ...
0
votes
1answer
25 views

Understanding Asymptotic Notation of a constant

How can I prove that if $f(n) = O(1)$ leads to $f(n) = \Omega(1)$ as well? I need a Formal definition of the meaning that a function $f(n) = O(1)$
0
votes
1answer
48 views

Prove that$ f(x)=\ln(x)$, where $ x>0$ is of exponential order.

Prove that$ f(x)=\ln(x)$, where $ x>0$ is of exponential order. I know that if there exists a constant a and positive constants $t_0$ and $M$ such that $|f(t)| \leq M e^{at}$ at for all $t > ...
-1
votes
1answer
26 views

The asymptote of $y=\mathrm{sinc}(t)$ as time increases

Is there any known approximate formula that maps decay percentage of $\mathrm{sinc}(t)$ with decaying time? Or in other words, is there a known asymptote of $y=\mathrm{sinc}(t)$ as time increases?
2
votes
1answer
31 views

Asymptotic series of Confluent Hypergeometric function $U(a,1,z) $ as $z \to 0$

Consider the Confluent hypergeometric function $U(a,b,z)$, which is a solution of the Kummer's Equation : $$zw''+(b-z)w'-aw=0$$ it has the following integral representation when $- \pi/2 < \arg ...
0
votes
1answer
28 views

Finding a function f(n) such that T(n) = O(f(n))

I need some help understanding how to prove that n log n in the equation below is the dominating term. i.e. Given the equation below, find function f(n) such that T(n) = $\theta$(f(n)): $T(n) = ...
1
vote
1answer
30 views

Proof that $\frac{1}{x\sqrt{x}}$ is $O(\frac{1}{x})$

My homework assignment is to proof that $\frac{1}{x\sqrt{x}}$ is $O(\frac{1}{x})$. I've seen different definitions of Big-Oh, but in my book it is defined as $|f(x)| \leq M \cdot|g(x)|$ for all $x ...
0
votes
2answers
50 views

Complexity of given recurrence [closed]

I need to find an upper bound for the function T defined by the following relations: $T(1) = 1$ $T(n) ≤ 34 · T(n/17) + 17n$ Answer need to be tight up to $O(1)$ factors. Please help to solve this ...
0
votes
1answer
35 views

What is this expression in big O notation?

$$2^{n-1} + 2^{n-1} + \ldots + 2$$ pretty basic question, but I'm afraid I don't know if it's $O(2^n)$ or $2^{O(n)}$
0
votes
2answers
31 views

Showing that $\log(\log(n))^{\log(n)}$ is $O(7^{\sqrt n})$

What's a straightforward way to prove that $\log(\log(n))^{\log(n)}$ is $O(7^{\sqrt n})$? (I'm dealing with Big O Notation)
0
votes
1answer
11 views

Does the natural (asymptotic) density of a set A change if a subset of A with natural density zero is subtracted from A?

I know that given two subsets of the Naturals A and B, if the natural density of A equals some non-zero real number a, and the natural density of B is zero, then the natural density of the symmetric ...
1
vote
1answer
35 views

How many infinite subsets of the Naturals have natural density (asymptotic density) zero?

Are there countably or uncountably many? I know that the set of all primes has density zero. Is there an obvious way of using that result to construct an uncountable family of such sets?
0
votes
1answer
45 views

Where exactly is $n\log n$ between $n$ and $n^2$?

If I have $n^{1.161}$ and $n^{1.58}$, how do they compare in terms of time complexity relative to $n\log n$? I only know that $n\log n$ is between $n$ and $n^2$. I would probably factor out $n$ ...
2
votes
3answers
32 views

Comparing growth rate of $n^{\log_2{5}}$ vs $n^2 \log{n}$

$\log_2{5}$ is 2.3219.. and thus $n^{\log_2{5}} = n^{2.3219}$. Comparing that with $n^2 \log{n}$ which already has an $n^2$ in front, which one grows faster? I notice that $n\log{n}$ is between ...
0
votes
1answer
27 views

Bound the number of different natural numbers that fit as a sum in $n$ as $n$ increases

Let me explain... I have $n$ integers, with $k$ different values where $k \leq n$. If I sum together the integers with same values I will get a set of different values frequencies. Now if I sum ...
10
votes
4answers
170 views

Calculate the infinite sum $\sum_{1}^\infty \frac{\log{n}}{2n-1}$

I would like to calculate an asymptotic expansion for the following infinite sum: $$\displaystyle \sum_{1}^N \frac{\log{n}}{2n-1}$$ when $N$ tends to $\infty$. I found that the asymptotic expansion ...
2
votes
3answers
32 views

Help formulating a proof showing two lists can be merged with 2n-1 comparisons

I need some help formulating a proof that shows that two lists of size n can be merged in 2n - 1 comparisons. I understand the essence behind it, but have difficulty proving it mathematically. I ...
5
votes
2answers
30 views

Big-$O$ for $\frac{1}{1-x}$

I would like to show as $x\rightarrow 0$ $$\frac{1}{1-x}= 1+x^2+x^3+\dots+x^n +O(x^{n+1})$$ My inclination is to multiply by $1-x$ to get: $1=(1-x)(1+x^2+\dots+x^n) +(1-x)O(x^{n+1})$ and then, for ...
2
votes
4answers
45 views

Finding growth bounds on Fibonacci Sequence

I've been working on this following problem: Find a constant $c< 1$ such that $F_n \leq 2^{cn}$ for all $n \geq 0$. I honestly have no idea where to begin on this. I've done plenty of proofs ...
0
votes
2answers
21 views

Proving the summation of a function as big theta of another function

Show that $\sum^n_i i^4\log^2i$ = $\Theta(n^5\log^2n)$ I am completely lost on how to solve this problem. I understand that $\Theta$ deals with the upper and lower bounds, so do we prove both big-oh ...
2
votes
1answer
18 views

Growth of modified binomial recurrence

The binomial coefficients $\binom{n}{r}$ satisfies $\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$. This means it is a solution of the equation $f(n,r)=f(n-1,r)+f(n-1,r-1)$, with initial conditions ...
2
votes
1answer
21 views

Using $f=O(g)$ to compare $f^2$ and $g^2$

When we have $f = O(g)$, does this work? $f^2 = O(g^2)$? If I have $n^2 = O(n^3)$, I think that $n^4= O(n^6)$ so I think this is valid. What about $2^f vs 2^g$? Does $f = O(g)$ imply $2^f = O(2^g)$? ...
0
votes
1answer
18 views

Growth rate of $n3^n$ vs $4^n$

Does the latter grow faster? I'm assuming that if we have a^n vs b^n, if b>a then a = O(b), but if there is a n term in front of a does that change it?
0
votes
1answer
18 views

Growth of binomial recurrence with different initial conditions

The binomial coefficients $\binom{n}{r}$ satisfies $\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$. This means it is a solution of the equation $f(n,r)=f(n-1,r)+f(n-1,r-1)$, with initial conditions ...
3
votes
0answers
36 views

Asymptotic expansion of a Fourier Transform as $\omega\rightarrow 0$

First of all, I do apologise if the question is not formulated in precise mathematical terms, but as a physics student I lack a formal background on rigorous functional analysis. Suppose we have a ...