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

Show that $1^k+2^k+\cdots+n^k$ is $\Omega (n^{k+1})$

...where k is a positive integer. The Big Oh case is not so hard. But how do I show that $1^k+2^k+\cdots+n^k$ is $\Omega (n^{k+1})$?
0
votes
0answers
7 views

Upper bounds of a recurrence

I need to find the asymptotic upper bounds in O notation for T(N) in two recurrences. Assuming that T(N) is constant for sufficiently small N, I need to make the bounds as tight as possible. T(N) = ...
0
votes
2answers
25 views

Prove or Disprove Θ

I want to prove or disprove that $3n^3 +n^2\log(n) = Θ(n^3)$. I'm aware that I will need to either prove or disprove both big-o and big-Ω to prove or disprove Θ. I am simply struggling to do so. Help ...
1
vote
2answers
20 views

Proof based on definition of big-o

I want to prove that n! = O(nn) based on the definition of big-O. I find it pretty easy to show that n! = O(nn) by simply showing that n (n-1) < n * n ... etc. However I can't figure out how to ...
0
votes
1answer
19 views

Prove the order of growth rates; Big-O

Order the growth rates of the following functions: $10^{−5}n$, $10^{2}\log n$, $3^n$, $n \log n$, $10^{−100}n^2 + 10^3n$, $n^n$ Then prove each of the relations. For example: if the ordering is A ...
0
votes
1answer
22 views

Prove that $\sum_{i=0}^{k} \lg \frac{n}{2^i} = \Theta(\lg^2 n)$

Show that if $n$ is a power of $2$, say $n = 2^k$, then we have the equality $\sum_{i=0}^{k} \lg \frac{n}{2^i} = \Theta(\lg^2 n)$. The first step is to prove $O(\lg^2n)$: $$ \lg \frac{2^k}{2^0} + \lg ...
0
votes
0answers
12 views

Can you analyze this identity involving the sum of divisors function and $rad(n)=\prod_{p\mid n}p$?

Let $\sigma(n)$ the sum of divisors function, then by Mobius inversion formula $$\sigma(n)=n-\sum_{\substack{d\mid n,d<n}}\sigma(d)\mu\left(\frac{n}{d}\right),$$ and since this function is ...
1
vote
1answer
18 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
21 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
38 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
34 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
16 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
17 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
29 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
22 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
37 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
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
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
27 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 ...
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
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
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
21 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
15 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
54 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
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
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
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
74 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
38 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 + ...