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
0answers
21 views

finding the n in Aymptotic notations

consider any quadratic function $f(n) = an^2 + bn + c$, where a, b, and c are constants and $a > 0$. Throwing away the lower-order terms and ignoring the constant yields $f(n)= \theta(n2)$. ...
1
vote
1answer
83 views

Expectation and Variance of random walks

Consider random walks of fixed length (e.g. $5$) starting at node $u$ in an undirected and connected graph with $N$ vertices. If a node $k$ has $N_k$ edges, the probability of the walk reaching any of ...
3
votes
1answer
68 views

Estimating an unusual infinite sum

I came across the following summation, which I would like to estimate. I only need an answer which is correct up to a constant multiple; one can assume that $a, b, c$ are real numbers in the range ...
1
vote
3answers
50 views

Prove line asymptotic to curve

I have a function denoted as: $f(x) = \frac{x}{1+e^\frac{1}{x}}$ I want to prove the line: $g(x)= \frac{x}{2} - \frac{1}{4}$ Is asymptotic (slant asymptote) to the above function when approaching ...
0
votes
3answers
40 views

Asymptotic notation (big Theta)

I'm currently in the process of analyzing runtimes for some given code (Karatsuba-ofman algorithm). I'm wondering if I'm correct in saying that $\Theta(\left\lceil n/2\right\rceil) + \Theta(n)$ is ...
1
vote
1answer
57 views

Big-theta notation

I was wondering about big-theta ($\Theta$) notation. A) Is $\Theta(n/2) \leq \Theta(n)$ for $n$ being an integer? I know that $n/2 = O(n)$, but does it also mean that $\Theta(n/2) \leq \Theta(n)$? ...
2
votes
3answers
41 views

Lower bound for the falling factorial $(2n)_{n}$

I'm looking for a lower bound for the falling factorial $$(2n)_{n}:= \frac{(2n)!}{n!}$$ I saw on Wikipedia that $n! > \sqrt{2{\pi}n}(\frac{n}{e})^n$ . So I assume that a possible lower bound ...
1
vote
1answer
29 views

Dealing with floor function in binomial coefficients

I'm trying to estimate $\binom{n}{\left \lfloor{\alpha n}\right \rfloor }$ asymptotically using Stirling's formula. However, I'm a little lost with what to do about the floor function here. In the ...
1
vote
1answer
34 views

Stuttering Subsequence Problem - Explain the example

I'm reading an article that deals with solving the stuttering subsequence problem in $\Theta (n)$. The article can be found here: http://www.cse.yorku.ca/~andy/pubs/Stutter.pdf Some background on ...
0
votes
3answers
48 views

Why does $\lim_{ t\to 0} \frac{o(t^2)}{t} = 0$?

Why does $\lim_{ t\to 0} \frac{o(t^2)}{t} = 0$? $\sqrt t = o(t^2) \implies \lim_{t\to 0} \frac{\sqrt t}{t} = \infty$ Maybe I don't understand completely the little-o notation.
2
votes
1answer
46 views

I need to show the following two limits

First, for $a>-1$: $$\lim_{n\to\infty}\frac{a+1}{n^{a+1}}\sum_{j=1}^nj^a = 1$$ Second, for $p>0$: $$\lim_{n\to\infty}\frac{e^a-1}{e^{a(n+1)}}\sum_{j=1}^ne^{aj} = 1$$ In particular, why do we ...
1
vote
1answer
16 views

Is Θ(⌈x/4⌉) = Θ(x)?

I'm currently working on aysmptotic notation. I know the basic laws of big theta, O, and omega. But I'm having a little confunsion in understanding simplifying the expressions (if that's even ...
2
votes
0answers
15 views

Leading behaviour of DE at infinity

This is taken from the book of Bender and Orszag, problem 3.44. Find the leading behavior as $x\rightarrow+\infty$ of the differential equation: $x^3y'' - (2x^3 -x^2)y' +(x^3-x^2-1)y=0$ Explain ...
0
votes
0answers
12 views

How to find asymptotic cost of matrix filling algorithm . Big O Notation

So I have a list X of N strings each of length M that will be called x_i for the ith index in X Example ...
0
votes
0answers
28 views

What are some examples of asymptotic expansions of integrals displaying the Stokes phenomenon?

With the term Stokes phenomenon we refer to how the asymptotic behaviour of a function can differ in different regions of the complex plane. What are some examples of asymptotic expansions of ...
1
vote
1answer
41 views

Big-O Constants Rule Question for not-monotonically non-decreasing functions

I know that for positive monotonically non-decreasing functions, f(n) and g(n), f(n) = O(g(n) + c) entails f (n) = O(g(n)) Why does this always true only for ...
2
votes
1answer
18 views

Expansion of cumulant transform

Verify the following expansion for a cumulant generating function of a random variable $X$. \begin{align} \kappa(t) & = \mu t + \frac{1}{2}\sigma^2t^2+\frac{1}{6}\rho_3\sigma^3t^3 + ...
3
votes
0answers
37 views

How does the Stokes phenomenon appear in the asymptotic expansion of $\int_0^\infty \frac{e^{-zt}}{1+t^4} dt$ for $z \to \infty$?

Consider the asymptotic $z \to \infty$ behaviour of the function $$ \tag 1 I_1(z) \equiv \int_0^\infty \frac{e^{-zt}}{1+t^4} dt.$$ This converges for $\Re(z) > 0$, and the asymptotic expansion $$ ...
0
votes
0answers
43 views

How to determine a Big-O estimate for an algorithm

This question has been mentioned in the forum but with a different approach. I need to determine a Big-O estimate for the number of operations of the algorithm below taking into account only additions ...
3
votes
3answers
81 views

Propose an algorithm to find a “celebrity”

A celebrity is a person that everyone knows, but he doesn't know anyone. If we think of a group of people as a graph, where if there is an arrow from $A$ to $B$ that means "$A$ knows $B$", then a ...
1
vote
2answers
46 views

Probability that colored balls are separated

Say we throw $b$ blue balls and $r$ red balls uniformly into $n$ boxes. The probability that no box contains a red as well as a blue ball is then, by the inclusion exclusion principle: $$p = ...
1
vote
1answer
24 views

Growth Rates of F(n) vs. F(n) + F(n-1) + … F(1)

I am trying to understand growth rates between a function and its sum recursively. For example I understand that if: $F(n) = n$ Then the sum $n + (n - 1) + ... 2 + 1 = \frac{n(n-1)}{2}$ which is ...
1
vote
0answers
43 views

Algorithm for matrix addition and multiplication

Let $m$, $n$ be integers such that $0 \leq m,n < N$. Define: Algorithm A: Computes $m + n$ in time $O(A(N))$ Algorithm B: Computes $m \cdot n$ in time $O(B(N))$ Algorithm C: Computes $m\bmod n$ ...
0
votes
2answers
29 views

Please provide additional information for a Big-O problem solution

I am studying a Big-O example but I just do not get the idea. I have already seen that this question was asked in this forum but I am still confused. Can someone please provide another explanation so ...
1
vote
1answer
30 views

Why do O(logn) & O(exp(n)) Have Polynomial & Non-Polynomial Running Time Complexities Respectively Despite Their Taylor Series?

I understand that a function, say $f(x)$, belongs to a class $O(g(x))$ iff: $$ \exists k > 0 \ \ \exists \ \forall n > n_0: |f(n)| \leq |g(n) \cdot k| $$ I also know that $log(x)$ is has ...
0
votes
0answers
34 views

About growth rate of function

Suppose the function $ d(T)→\infty $as $ T→∞ $, what is the appropriate growth rate of $ d(T) $ in order that $ d(T)^{2d(T)-1}/T^c→0 $ with $c$ being a constant? Thanks very much for your kind help. ...
1
vote
1answer
19 views

limiting variances of iid sample mean

In the book Statistical Inference (George Casella 2nd ed.), page 470, there is an example: $\bar{X}_n$ is the mean of $n$ iid observations, and E$X=\mu$, $\operatorname{Var}X=\sigma^2$. "If we take ...
0
votes
3answers
57 views

Showing that $4n + 3n \log_2n$ is $O(n\log_2n)$

I need to prove that: $$ 4n+3n\log_2n \text{ is } O(n\log_2n) $$ How can I find $c$ and $n_0$ for $3n\log_2n$? Also, using the big-Oh definition, I need to show that: If $g_1(n)$ is $O(f(n))$ and ...
1
vote
1answer
12 views

Is the integral finite if the integrand is $o(x^{-1})$?

According to theorem 2.2 in this file http://www.stat.umn.edu/geyer/old06/5101/notes/n1.pdf If $\lim_{x\to\infty} \frac{g(x)}{x^{-1}} =0$, nothing can be said about the existence of ...
0
votes
1answer
12 views

How do I determine a percentage increase of a function caused by increasing the input?

Suppose you have algorithms with the five running times listed below. (Assume these are the exact running times.) How much slower do each of these algorithms get when you (a) double the input size, or ...
2
votes
2answers
38 views

Prove $\frac{-\log(1-x)}{x(1-x)}=1+(1+1/2)x+(1+1/2+1/3)x^3+…$

Let $0<x<1$. How can i prove the following identity: $$\frac{-\log(1-x)}{x(1-x)}=1+(1+1/2)x+(1+1/2+1/3)x^3+...\ \ .$$
4
votes
1answer
91 views

Asymptotic evaluation of integral of algebraic function

I am wondering what techniques exist for the asymptotic evaluation of integrals. Consider the integral $$ I(\lambda) = \int_1^\lambda dx \sqrt{1-\frac 1 x} = \sqrt \lambda \sqrt{\lambda - 1}- ...
1
vote
1answer
39 views

Probability of picking each of m elements at least once after n trials.

Suppose I have 10^9 distinct elements, and an equal probability of picking each one in a given trial. How many trials must be conducted for the probability of having picked every element at least once ...
0
votes
2answers
21 views

How can I prove that Cx will intersect x^2

I want to disprove $ cx \geq x^2 \ \forall \ x $ where c is a real number. (i.e. show that x^2 is not O(x) ) So it seems that I can show that the two must intersect at some point ... if I divide both ...
0
votes
0answers
18 views

Different Upper and Lower Bound

Is there a function or algorithms whose upper bound and lower bound are different? For example f(X) i.e f(X) = O(X^2) and f(X) = Omega(X)
0
votes
2answers
64 views

Asymptotics of $\sum \sqrt{k}$ and $\sum (-1)^k\sqrt{k}$

I was playing around with series recently and asymptotics of $\sum \sqrt{k}$ and $\sum (-1)^k\sqrt{k}$ were required to solve another problem. I have dealt with the first one using an integral ...
0
votes
1answer
37 views

Name of the difference between an asymptote and the curve that approaches it

Consider a function, say a hyperbola, and its asymptote. Is there a specific term for the difference between the two? Answers specific to hyperbola, as well as answers about general terminology, are ...
1
vote
1answer
73 views

Asymptotic Expansion of an Integral involving Modified Bessel Functions

I do not have enough experience with the asymptotic expansion of integrals especially involving Bessel functions. I appreciate any feedback that you guys provide. Here is the problem. Let $a$ and $b$ ...
1
vote
1answer
24 views

Running Time Question

In what situations would a function of $\theta(n^2)$ perform better than $\theta(n \log n)$? I noticed that in comparing the two, they intersect at $n = 4$. After this, $n \log n$ takes over as ...
3
votes
1answer
35 views

How to give an upper bound for a solution of $T(n) = T(0.25n) + T(0.75n) + O(n)$?

We have an algorithm which can be described the recurrence formula: $T(n) = T(\frac{n}{4}) + T(\frac{3n}{4}) + O(n)$ and for $n\le 100$: $T(n) = O(1)$. How to show that $T(n) = O(n \log n)$? ...
0
votes
2answers
14 views

Dominance and Big Oh problem

What is the dominant term in the following expression? 100n + 0.01*(n^2) It is confusing because the power function should be growing faster than the linear function regardless the constants. But ...
3
votes
1answer
43 views

Algebraic number with bounded coefficients

How many algebraic numbers $z$ are there satisfying $P(z)=0$ where $P(z)$ is some polynomial with integer coefficients of degree less than or equal to $n$ such that the absolute value of every ...
2
votes
1answer
32 views

Asymptotic solution to inequality $x < k \ln(1+x)$

What is an upper-bound on $x$, given that $x < k \ln(1+x)$? I believe that the solution is something of the form $\mathcal{O}(k \ln k)$ but I am unable to prove this. This is my first encounter ...
1
vote
2answers
58 views

Find the asymptotes of the Parametric equation?

Consider $$ x(t) = 2 e^{-t} + 3e^{2t}$$ $$y(t) = 5 e^{-t} + 2 e^{2t}$$ which represents a non rectilinear paths Horizontal and Verical Asymptotes : If $t \rightarrow +\infty \ \ or \ \ -\infty$, ...
0
votes
1answer
18 views

Confirm the answer to compute the asymptotic solution to the problem

I have the following problem The solution I derived is $O(g(n))$ where $C = 1, n > 1$. Is this solution correct ?
0
votes
0answers
10 views

Upper bound for $T(n) = T(2n/3) + t(4n/9) + O(n)$

I got $T(n) = O(n^{11/9})$ as the answer. I just wanted to confirm if this is a correct bound and is there any tighter bound possible than this.
1
vote
1answer
37 views

Run time/Efficiency of finding Least Common Multiple

The algorithm is: $$\mathrm{lcm}(x,y)=\frac{xy}{\gcd(x,y)}$$ And we can use the Euclidean algorithm for finding $\gcd$. How is the complexity for above method $O(n^3)$, if $x,y$ can at ...
2
votes
0answers
46 views

Asymptotic expansion of integral of e^(-t)/t^n

So we study $$f_{n}(x) = \int_x^{+\infty} \! \frac{e^{-t}}{t^{n}} \, \mathrm{d}t, \quad n \in \mathbb{N^{*}}$$. I've shown that for every $n$, $f_{n}(x) \sim_{+\infty} \frac{e^{-x}}{x^{n}}$. Now ...
1
vote
1answer
77 views

Infinite sum of asymptotic expansions

I have a question about an infinite sum of asymptotic expansions: Assume that $f_k(x)\sim a_{0k}+\dfrac{a_{1k}}{x}+\dfrac{a_{2k}}{x^2}+\cdots$ with $a_{0k}\leq \dfrac{1}{k^2}$, $a_{1k}\leq ...
0
votes
1answer
30 views

How do limit cycles explain curvilinear asymptotes?

I'm a 17 years old and I have no clue about a concept known as limit cycles. I looked it up and I understand it represents the orbit of functions approaching other A person told me that limit cycles ...