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

Show that $\lim_{n\rightarrow \infty} (1-\omega(\frac{1}{n}))^n=0$ and $\lim_{n\rightarrow \infty} (1-o(\frac{1}{n}))^n=1$

Could you help me to show that (1) $\lim_{n\rightarrow \infty} (1-\omega(\frac{1}{n}))^n=0$ (2) $\lim_{n\rightarrow \infty} (1-o(\frac{1}{n}))^n=1$ where $o(\cdot)$ is little $o$ notation described ...
0
votes
0answers
13 views

Asymptotic power of a test

Do you have any insight on the following statement Consider a test with a test statistic weakly convergent to a continuous distribution under any alternative and such that the finite sample power at ...
2
votes
1answer
38 views

Inquiry on big $O$ notation

As a deeply enthusiastic prospective undergraduate student, there are is a fact that i'm still to completely understand about the big $O$ notation, namely: Let $f(x), g(x) \neq x$ be nonconstant ...
0
votes
0answers
28 views

Find the simplest $g(n)$ such that $f(n) \in \Theta(g(n))$

Let $f(n) = \sum_{i=1}^n i^{-1}$. Would the simplest $g(n)$ be $1$? If we let $g(n) = 1$, then for all $n > 1$, $g(n) \le f(n)$. To construct an upper bound, observe that since $n$ is finite, ...
0
votes
2answers
16 views

asymptotic and monotonically increasing properties of prime factorization function?

Questions We define $A(x)= \text{number of prime factors of x}$ For example $A(2 \times 3^2) = 3$ I noticed when $s_k = \frac{N!}{\prod_j n_j}$ and $\sum_{j} n_j = N$ $$ s_1 < s_2 \implies ...
2
votes
1answer
92 views

Asymptotics of “ugly” function elucidate Goldbach's conjecture?

Question We now define the following "ugly" function: $$ A_c(s,r,n,m) = \begin{cases} 1 & \text{ if only $sr+nm=2c$ } \\ 0 & \text{otherwise} \end{cases} $$ How does the ...
0
votes
1answer
49 views

Accelerated Order of Convergence

Let $m > 0$ and $ a:[0,1] \rightarrow \mathbb R$ be a function with $a(\epsilon) \rightarrow 0$. Then $ \epsilon^m a(\epsilon) \rightarrow 0 $ for $ \epsilon \rightarrow 0$. But is $ \epsilon^m ...
3
votes
1answer
41 views

Modified Laplace's method

In the application of Laplace method (or steepest descent) it is often assumed that the dependence on the factor N, on which we are expanding the integral, is only in the argument of the exponential. ...
0
votes
1answer
20 views

Find a function $f(n)$ such that neither $f(n) = O(log n)$ nor $f(n) = \Omega(n)$ holds.

Any hints on this problem? I want to find a function $f(n)$ which is: NOT $f(n) = O(log n)$ NOT $f(n) = \Omega(n)$ So it must hold that: $c_1 * log n < f(n) < c_2 * n$ and $c_1, c_2$ are ...
0
votes
1answer
18 views

Asymptotic bounds on sum of primes

Let $p_i$ denote the $i$th prime number, and let $p_k\#$ denote the $k$th primorial, $p_k\# \overset{\textrm{def}}= \prod_{i \le k} p_i$. I am interested in asymptotic upper bounds for the ...
4
votes
2answers
185 views

Euler-Maclaurin Summation

Using EM summation formula estimate $$ \sum_{k=1}^n \sqrt k $$ up to the term involving $\frac{1}{\sqrt n}$ My attempt is $$ \sum_{k=1}^n \sqrt k = \frac{2 \sqrt{n^3}}{3} -\frac{2}{3} + \frac 1 ...
3
votes
0answers
33 views

Distinct prime factorization function formulation to find mobius function?

Background I recently noticed the following: $$ S(x)=\sum_{r=1}^\infty x^{p_r} $$ where $p_r$ is the $r$'th prime: $$ \sum_{r=1}^\infty S(x^r) = \sum_{r=1}^\infty \frac{x^{p_r}}{(1-x^{p_r})} $$ ...
0
votes
0answers
3 views

Asymptotic runtime of $f(n)$ in the Master Method

The Master Method helps us solve recurrences of the form: $$T(n)=aT(\frac{n}{b})+f(n).$$ If $f(n)$ is convoluted, is there any point in examining the terms beyond the highest order ones? Suppose for ...
0
votes
2answers
57 views

Big-Oh Analysis of For Loop

I have the following for loop: sum = 0 for i = 1 to n do for j = 1 to i^3 do for k = 1 to j do sum++ What is the strategy to determine ...
0
votes
0answers
23 views

Master Theorem for common recurrence

I have the following recurrence: $$T(n) = T\bigg(\frac{n}{2}\bigg) + O(n)$$ And I am trying to find the time complexity using the master theorem. So I have: $a = 1, b = 2$ $f(n) = O(n) = c(n)$ ...
1
vote
0answers
16 views

Estimating the sum $\sum_{y \in \Bbb{Z}^d} (|y|+1)^{-\alpha}(|x-y|+1)^{-\beta}$ as $|x| \to \infty$

I would like to know a rather precise asymptotics of the sum $$ S(x) = S_{\alpha,\beta}(x) := \sum_{y \in \Bbb{Z}^d} \frac{1}{(|y| + 1)^{\alpha}(|x-y| + 1)^{\beta}}$$ as $|x| \to \infty$. Here, ...
2
votes
1answer
88 views

Swapping the order of limits in combinatoric?

Part $A$ Let a power series be $ \sum_{r=1}^\infty x^{a_r}$ Now, we are interested square of the power series with the condition: $$ \sum_{m=1}^\infty \sum_{n=1}^\infty x^{a_m + a_n} = ...
0
votes
0answers
26 views

The minimum of two big-O functions

Suppose we have the following lower and upper bounds for an invariant $\chi(G_N)$, where $G_N$ is a graph on $N$ vertices, $N=f(k,n,m) $ and $N,k,n,m\in \mathbb{N}$: $$ ...
1
vote
0answers
7 views

Calculation of Running time of array when size increase by constant

I am learning data structure and running time calculation. I got a problem to understand the running time calculation of increasing the size of the array. 1) if we increase the size of the array by ...
0
votes
0answers
16 views

Big-Oh, Big-Omega, Big-Theta determination

I am given a recurrence relation and told to solve it. Once we solve it we are supposed to determine whether it is in $O(f(n)), \Omega(f(n))$, or $\Theta(f(n))$. The relation is $t_n = 2nt_{n-1}$. ...
0
votes
0answers
21 views

Constant Moment Generating Function and degenerate Random variable .

Let $\{X_n\}$ be such that $X_n$ has a binomial distribution with parameters $n$ and $p=\lambda /n$ , then as known $X_n$ will converge in distribution to $Y$ which has a Poisson distribution with ...
0
votes
1answer
43 views

What is the difference between “DTIME” and “Big O” notation?

I have some understanding of "big O" and "little O" notation. I have heard of "DTIME" but have not had formal education or training regarding its use. Can someone explain the difference (or ...
0
votes
1answer
29 views

There is no algorithm which has a runtime of $O(n^2)$ and $\Theta(n^\frac{7}{2})$

How can I proof that there exists no algorithm which has a runtime of $O(n^2)$ and $\theta(n^{\frac{7}{2}})$? Or is this possible because logically I would say that if a function is ...
0
votes
1answer
115 views

What are the smallest amount of numbers required to generate all the even numbers?

Viewpoint 1 To generate the even numbers $<n$ the smallest amount of numbers we need about $O (\sqrt{n})$ (by summing only $2$ elements) Hence, consider the series: $$ ( \sum_{r=1}^n x^{b_r})^2 ...
0
votes
0answers
41 views

Asymptotic expansion of $ \int_{a}^{x} t^{t} ~ \mathrm{d}{t} $ as $ x \to \infty $.

I am trying to solve Exercise Problem 1.13 from Estrada and Kanwal’s A Distributional Approach to Asymptotics, Theory and Applications without any luck. Actually, I think that it is wrong. ...
0
votes
0answers
178 views

Reformulation of Goldbach's Conjecture as optimization problem correct?

Question I think I managed to reformulate a stronger version of Goldbach's conjecture as an optimization problem: $$ \frac{\partial F_n}{\partial a_n} = \frac{\partial F_n}{\partial \overline a_n} ...
1
vote
1answer
23 views

Big O Definition

There is a formal definition for the Big O notation in Wikipedia. Up to now I have come across Big O in Numerical Analysis, Calculus and Algorithms which all are pretty distinct fields. What I am ...
0
votes
0answers
59 views

An asymptotic involving fractional parts

I guess this is quite well known, but I was not able to find the related result. I want to find an asymptotic estimate for the expression $\sum_{k=1} ^{C\lfloor L \rfloor} \sum_{n=1} ^{\infty} ...
3
votes
2answers
78 views

How to get the short time asymptotics of this integral?

The integral is like this: $$ \int_0^\infty \mathrm{d} x \frac{\cos[2t\cosh(\frac{\pi x}{2})]}{1+x^2} $$ The short time asymptotics is like this (some constant maybe missing): $$ \sim \frac{1}{\ln ...
1
vote
0answers
83 views

Existence of a $G(x)$ that can generate all the even numbers?

Question This is a "spin-off" question of: Reformulation of Goldbach's Conjecture as optimization problem correct? I was wondering if a function existed such that: $$ G(x)^2 = ...
1
vote
2answers
39 views

What is the correct method of finding the leading order behavior of a function in a given limit?

I am kind of confused about finding the correct leading order behavior of a function. Example: If I want to understand the behavior of the following function $$f(x)=\coth(x)-\frac{1}{x}$$ I can ...
-1
votes
0answers
32 views

The number of operations executed by algorithms A and B are $12n^3 + 40n \log n$ and $5n^4 -100n^2$ respectively.

The number of operations executed by algorithms A and B are $12n^3 + 40n \log n$ and $5n^4 -100n^2$ respectively. Determine an $n_0$ such that $B > A$ for $n \geq n_0$. so i got that $12n^3 + ...
-1
votes
0answers
61 views

Solve for $n$: $12n^3 + 40n \log n = 5n^4 -100n^2$

Need to solve for $n$: $12n^3 + 40n \log n = 5n^4 -100n^2$ tried it out and my answer isn't making sense
4
votes
1answer
51 views

A simpler way of showing $\int_1^n \frac{t-\lfloor{t\rfloor}}{t}dt = \frac{1}{2}\log{n} +O(1)$

As part of an exercise (whose eventual purpose is to derive Stirling's approximation), I had to obtain the relation$\int_1^n \frac{t-\lfloor{t\rfloor}}{t}dt = \frac{1}{2}\log{n} + O(1)$ (where $n$ is ...
6
votes
1answer
448 views

Evaluating a limit of the truncated exponential series motivated by the prime number theorem for $k$ distinct prime factors.

If $\pi_k(n)$ is the cardinality of numbers with k factors (repetitions included) less than or equal n, the generalized Prime Number Theorem is: $$\pi_k(n)\sim \frac{n}{\ln n} \frac{(\ln \ln ...
2
votes
0answers
18 views

higher-order (3+) Taylor expansion of a likelihood function

I was wondering what is the effect if I replace the second derivative of the log-likelihood ("Likelihood" hereafter) function with its expectation in a higher-order Taylor expansion of the likelihood ...
0
votes
0answers
24 views

How to expand in terms of inverse logarithms?

I'm currently working with a matched asymptotic expansion problem. Currently, I have a function $f$ that can be expanded as: $$f = f_0 + \frac{f_1}{\ln{\epsilon}} + \frac{f_2}{(\ln{\epsilon})^2} + ...
2
votes
1answer
24 views

Big O Notation logarithms

I'm having trouble with these two Big O notation proofs (b) $(n + \log_2 n)^5 = \Theta(n^5).$ (b) $(\log_2 n)^5 = O(\log_2 n^5).$ For the first one, I'm having trouble finding a $c$ value ...
1
vote
1answer
82 views

Solving limits without l'Hopital

I've encountered several limits that need to be solved in order to calculate the coefficients in asymptotic formulas for elementary functions, e.g.: $$ \lim_{x \to 0}\frac{\sin x -x}{x^3} $$ $$ ...
0
votes
1answer
23 views

Big-O complexity of $2t(\frac{n}{2}) + n^3$

I'm trying to determine the Big-O complexity of the listed equation and want to know if my approach is valid. I tried using the Master method. It appears to be a case $3$ type problem to me, where ...
3
votes
1answer
71 views

Asymptotic relation for the following series?

Questions Is the asymptotic relationship correct? How do I determine $c_1$ and $\kappa$? As, $|s| \to 0$ $$ \sum_{r=1}^\infty s^r \ln(r) \sim c_1 \sqrt{s} + (\kappa - 1 + \frac{\ln(2 \pi)}{2} ...
3
votes
1answer
93 views

The expected value of the $k$th order statistic of iid geometrically distributed rvs, and its asympotic expansion.

I have read the paper Combinatorics of geometrically distributed random variables: Left-to-right maxima. In the paper, the largest order statistic $X_{n:n}$ (i.e., $\max\{X_1,X_2,\ldots,X_n\}$) is ...
1
vote
1answer
12 views

If $f(n)$ and $g(n)$ are both $\Theta (h(n))$ then is it true that $f(n)$ is $\Theta (g(n))$ and $g(n)$ is $\Theta (f(n))$?

My question is exactly what the title says. If two functions are $\Theta$ of another function then are they $\Theta$ of each other. I know that this is not the case with big $O$ but does it work with ...
2
votes
3answers
47 views

Which is asymptotically larger $3n^{\sqrt{n}}$ or $2^{\sqrt{n}\log_{2} n}$?

Which is asymptotically larger $3n^{\sqrt{n}}$ or $2^{\sqrt{n}\log_{2} n}$? What I have done is taken $log$ on both sides, which gives $$ f(n) =\log (3n)^{\sqrt n} $$ and $$ g(n) = \log (2)^{\sqrt n ...
2
votes
3answers
39 views

Finding the oblique asymptote of $f(x)=2x\tan^{-1}(x)$

I have problems with the computation of the oblique asymptote for the function $$f(x)=2x\tan^{-1}(x)$$ I started by stating that $y = mx + b$ is the equation of the oblique asymptote. Next I looked ...
1
vote
2answers
93 views

Describe an $O(N)$ time algorithm for determining if there is an integer in a sequence $A$ and an integer in a sequence $B$ such that $x = a + b$

Unfortunately I couldn't make the title for my question long and I didn't really know how to shorten it, so there are some added constraints: Let $A$ and $B$ be two sequences of $n$ integers each, in ...
2
votes
1answer
30 views

Is $O(n^k \log n)$ of smaller time complexity than $O(n^{k+\epsilon})$?

Is it true that asymptotically, $O(n^k \log n)$ is of smaller time complexity than $O(n^{k+\epsilon})$ for $\epsilon>0$? How might I prove this one way or the other?
12
votes
1answer
121 views

Divergent function of ratio must be logarithm

Given. Consider two functions $F(t)$ and $r(t,x)$ such that $\lim_{t\to\infty} F(t) = \infty$ and $\lim_{t\to\infty} r(t,x)$ is finite for any $x$. ($x$ and $t$ are always positive in what follows.) ...
2
votes
0answers
97 views

Number-theoretic asymptotic looks false but is true?

Question Let $p_r$ be the $r'th$ prime. Is it true that, $$\sum_{r=1}^\infty s^r \ln(p_r) \sim \frac{s}{(1-s)} $$ I know this looks bizarre but kindly consider the argument below. I'm also ...
11
votes
2answers
369 views

Known bounds for the number of groups of a given order.

The number of nonisomorphic groups of order $n$ is usually called $\nu(n)$. I found a very good survey about the values. $\nu(n)$ is completely known absolutely up to $n=2047$, and for many other ...