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

learn more… | top users | synonyms (1)

1
vote
0answers
46 views

Proving $n^{10\log(n)} = O((\log^n(n))$

I need to decide which of the following is correct: $n^{10\log(n)} = O((\log^n(n))$ $n^{10\log(n)} = \Theta((\log^n(n))$ $n^{10\log(n)} = \Omega((\log^n(n))$ So I'm saying $n^{10\log(n)} = ...
0
votes
0answers
13 views

Question about big omega proof

I'm not sure if I should post it here or in StackOverflow, but anyway... Prove that: $n^5-2\log{n}=\Omega{(n^5)}$. Proof: We need to find $c, n_0 \geq0$ such that, for all $n \geq n_0$, ...
1
vote
0answers
27 views

Asymptotic expansion of a Laplace-type integral with a “manifold of maxima”

Consider the integral $$ I(\alpha)=\int_0^1 dx_1 \int_0^1 dy_1\int_{x_1}^1dx_2\int_{y_1}^1dy_2\,e^{-\alpha(x_2-x_1)(y_2-y_1)} $$ in the limit $\alpha\rightarrow\infty$. To find the asymptotic ...
1
vote
0answers
53 views

Asymptotic large order approximation for Bessel function expression

How does one find the asymptotic large order approximation for $\sup_{0\le x\le\infty} \left(\sqrt{x} J_n(x)\right)$, where $J_n$ is the Bessel function of the first kind and order $n$. This is NOT a ...
4
votes
0answers
66 views

Growth of $n!!\dots !$

The asymptotic growth of the factorial function $n!$ is famously given by Stirling's formula as $$n! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n$$ Is there a similar formula for the iterated ...
0
votes
1answer
27 views

Suppose that $f (x)$ is $O(g(x))$. Does it follow that $2^{f(x)}$ is $O(2^{g(x)})$?

Suppose that $f(x)$ is $O(g(x))$. Does it follow that ? First, I start from for some $c$ is a real number. Then, I find . But, if i start from , I just find . I confused with that different form.
0
votes
0answers
20 views

How to do this asymptotic task?

Let a(n) be the amount of natural numbers, which are smaller than n, and their prime divisors are only 2 and 3. For example: 6 is good, because it only has 2 and 3 has prime divisors, but 10 is not ...
1
vote
1answer
28 views

Suppose that $f (x) =O(g(x))$. Does it follow that $\log |f (x)| =O(log |g(x)|)$?

Suppose that $f(x)=O(g(x))$. Does it follow that $\log |f (x)|=O(log |g(x)|)$? I start from $f(x)=O(g(x))$, until I get Does it mean $\log |f (x)|=O(log |g(x)|)$?
0
votes
0answers
21 views

Non-deterministic multiplication algorithms

Are there any algorithms for non-deterministic Turing machines that can compute the decision problem $mn=x$ (where $m=O(n),x=O(n^2)$) faster than the equivalent deterministic algorithm? Equivalently, ...
0
votes
1answer
38 views

How to solve this recurrence, $T(n) = T(\sqrt{n}) + n$ using recursive tree method?

How to solve this recurrence, $ T(n) = T(\sqrt{n}) + n $ using recursive tree method? I draw the tree and got a sum, $ T(n) = T(1) + ( n + n^{\frac 12} +n^{\frac 14}+n^{\frac 18}+\ldots +1) $ I need ...
2
votes
2answers
33 views

How to prove that $2^{n+1} = \Theta(2^n)$?

I have a problem were I need to prove big theta. $f(n) = 2^{n+1} = Θ(2^n)$. I proved that this was true for big O but I'm not sure how to go about proving big Theta.
1
vote
4answers
51 views

Does the inequality $ n! > A \cdot B^{2n+1}$ hold for sufficiently large $n$?

Suppose $A,B >0$ are given constants. Is it possible to find a large enough $n \in \mathbb{N}$ such that $$ n! > A \cdot B^{2n+1}?$$
3
votes
0answers
33 views

Proof $\mathcal{O}(f(n)) = \mathcal{O}(g(n)) \iff f(n) \in O(g(n)) \land g(n) \in \mathcal{O}(f(n))$

There is an exercise that ask me to prove this logic formula about the complexity of algorithms: $\mathcal{O}(f(n)) = \mathcal{O}(g(n)) \iff f(n) \in O(g(n)) \land g(n) \in \mathcal{O}(f(n))$ ...
0
votes
2answers
20 views

How would I go about proving these.

I need to prove or disprove these two problems, but I'm not sure I did it right. $$(a).\quad f(n) = 2^n+1 = O(2^n)\\ (b).\quad f(n) = 2^n+1 = Θ(2^n) .$$ What I tried for the first one is, ...
1
vote
1answer
23 views

Simplifying $f(n)$ by substituting, for $n$, an appropriately chosen function $n(x)$ to observe limiting behaviour of $f(n)$. Is this justified?

Say, I'm comparing two functions $f(n) = (ln(n))^2$ and $ g(n) = n^{0.01}$ as $n \rightarrow \infty$, by evaluating $\lim_{n \rightarrow \infty } \frac{f(n)}{g(n)} = \lim_{n \rightarrow ...
12
votes
2answers
248 views

When is this sum of perfect powers bounded

For any positive integers $n,d$, let $$ A_d(n)=\frac{\sum_{k=1}^n k^{2d}}{n(n+1)(2n+1)} $$ It is easy to see (and well-known) that for fixed $d$, $A_d(.)$ is a polynomial of degree $2d-2$. Writing ...
0
votes
0answers
8 views

Comparing Growth Rates

Suppose I want to compare the growth rate of some function $f(x)$ as $x\to a$ and another function $g(x)$ as $x\to b$. How do I go about doing that? For example, I want to decide whether ...
4
votes
1answer
47 views

Upper bound for $\prod_{ 5 \leq p <n} p^{\frac{n}{p-1}}$

Does anyone know how I could get a good upper bound for the following: $$R := \prod_{\substack{ p \; \text{prime} \\ 5 \leq p < n}}p^{\frac{n}{p-1}}$$ I'm not that skilled at asymptotic analysis ...
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
94 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
70 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
42 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
33 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
38 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
16 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
25 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
31 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
45 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
19 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
41 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
51 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
91 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
51 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
26 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
50 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
32 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
31 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
22 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
40 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
92 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}- ...