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
1answer
14 views

$a_n\geq b_n$ for $n>\bar{n}$ implies $\limsup_{n\rightarrow \infty}a_n\geq \limsup_{n\rightarrow \infty}b_n$

Consider two sequences of real numbers $\{a_n\}_n, \{b_n\}_n$. I know that if $a_n\geq b_n$ $\forall n$ then $\limsup_{n\rightarrow \infty}a_n\geq \limsup_{n\rightarrow \infty}b_n$. Suppose ...
-1
votes
0answers
19 views

Is $ \lfloor {\log(n)} \rfloor!$ or $ \lfloor {\log(\log(n))} \rfloor!$ polynomially bounded? [on hold]

Which of these is is polynomially bounded: $ \lfloor {\log(n)} \rfloor!$ $ \lfloor {\log(\log(n))} \rfloor!$ I think both are but I can't prove it.
2
votes
2answers
33 views

Can you get a closed-form for $\sum_{j=0}^{\infty}\frac{2^{2j-1}B_{2j}}{(2j)!}$?

Let $B_{k}$ the kth Bernoulli number, then using their asymptotic I can justify the absolute convergence of this series $$\sum_{j=0}^{\infty}\frac{2^{2j-1}B_{2j}}{(2j)!},$$ since, if there are no ...
1
vote
0answers
18 views

Big-Theta - asymptotic bound - is solution sufficient enough?

I am wondering is my solution sufficient enough (or detailed enough) for the following question? or it is even a valid solution? Question: Find a tight asymptotic bound ($\Theta$) in terms of the ...
0
votes
1answer
29 views

Bounded away sequence implications

Consider the sequence $\{\sqrt{n}|a_n-a|\}_n$ where $a_n, a \in \mathbb{R}$. Assume $\{\sqrt{n}|a_n-a|\}_n$ is bounded away from $0$ and $\infty$. Is this equivalent to or sufficient or necessary for ...
-1
votes
0answers
15 views

$f(a)\leq g(a)\in (o(a))^{\frac{1}{2}}$ implies $f(a)\in o(a)$

Consider the real-valued functions $f,g$ such that $f(a)\leq g(a)\in (o(a))^{\frac{1}{2}}$ as $a \rightarrow 0$, where $o(\cdot)$ denotes little o notation explained here. In order to show $f(a)\in ...
1
vote
1answer
14 views

Implications of $n a_n=O((n^{\frac{1}{\alpha}}|b_n|)^\alpha)$

Consider two sequences of real numbers $\{a_n\}_n$, $\{b_n\}_n$. Suppose $n a_n=O((n^{\frac{1}{\alpha}}|b_n|)^\alpha)$ where $\alpha \in \mathbb{R}$, $na_n\geq 0$ and big $O$ notation is explained ...
4
votes
2answers
39 views

Sequence bounded away from $0$ and $2$

Suppose I have a sequence of real numbers $\{a_n\}_n$ and I'm told that $\{a_n\}_n$ is bounded away from $0$ and $2$. (1) What does it mean exactly? My thinking is that it means $a_n\neq 0$ and $a_n ...
1
vote
0answers
27 views

What is the probaility that two random permutations have same order?

I am interested in the orders of random permutations. Since the law of the log of the order of a permutation converges to a normal law (for instance Erdös-Turan Statistical group theory III), one ...
1
vote
2answers
35 views

Is it true that $ f(n) = O(g(n))$ implies $g(n) = O(f(n))$

So I have this is an assignment for algorithms. I've googled a lot, read the chapter in the book about big Oh notation, and I understand the concept. I do not however understand how to prove it. I ...
0
votes
0answers
21 views

Solve the Recurrence Relation to Get a Theta Bound

If I have $T(n)=T(n-5)+n$, how would I go about using induction to find a $\Theta$ bound for this. I was able to use a tree method to get that the bounds should be about $\frac{n^2}{5}$, but I am ...
1
vote
2answers
35 views

Analyze for loop with if statement

I have this rather complicated loop: sum=0 for i=1 to n do for j=1 to i^2 do if(j (mod i) = 0) then for k=1 to j do sum++ ...
0
votes
0answers
34 views

Algorithm For Honest vs. Dishonest People

Consider a group of people. When two are taken and asked if the other is honest, they may each either reply that the other is honest, dishonest, or they may report that one is honest and the other is ...
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 ...
1
vote
2answers
31 views

Order of growth of logarithms, compared to linear

I think it is true that any power of a logarithm, no matter how big, will eventually grow slower than a linear function with positive slope. Is it true that for any exponent $m>0$ (no matter how ...
0
votes
0answers
12 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
29 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
25 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
15 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 ...
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 ...
2
votes
1answer
91 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
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 ...
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
0answers
20 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
13 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, ...
0
votes
2answers
53 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 ...
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
25 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}$: $$ ...
0
votes
0answers
14 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
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 ...
2
votes
1answer
87 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
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
40 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
1answer
40 views

Product of Two systems with the same asymptotically stable fixed points

I am trying to figure out the nature of a new dynamical system that is equal to the product of two dynamical systems with the same asymptotically stable fixed point. For instance, if i have $x' = ...
1
vote
1answer
22 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
72 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
37 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 + ...
0
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
0
votes
1answer
36 views

Show that if $d(n) = O(f(n))$ and $e(n) = O(g(n))$ then $d(n) – e(n) \neq O(f(n) – g(n))$ [closed]

I got a little problem... Show that if $d(n) = O(f(n))$ and $e(n) = O(g(n))$ then $d(n) – e(n) \neq O(f(n) – g(n))$ The opposite is supposedly true (+ instead of -).
0
votes
0answers
151 views
+50

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
votes
0answers
52 views

Asymptotically closer to $\log_{m}n!$ [closed]

Which of the following sums is asymptotically closer to $log_{m}n!$ and why? $$\sum_{k=1}^{n}\left \lfloor \log _{m}k \right \rfloor$$ or $$\sum_{k=1}^{n}\left \lceil log_{m}k\right \rceil$$ which is ...
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 ...
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
0answers
16 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 ...