# Tagged Questions

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

15 views

### Growth function and one misunderstanding point?!

I have a question about Growth and Asymptotic notation topic. My question is as follows: $2^n$ > $n^{log_2{(n)}}$ is True. anyone could say how we can deduce that this fact is true?
22 views

### Big O notation for summation function

May be I am missing something very simple but I am finding it hard to understand why Big O for summation is O(n^2). I know that Big O for summation comes from fact that sum(1 to n) = n(n+1)/2. But if ...
28 views

### How do you solve the following questions on asymptotic analysis. Please share your approach. [on hold]

Check this image: I have read about the three notations but I'm unable to use the concepts to solve questions like this.
36 views

### Would these witnesses satisfy this big-O function?

I'm trying to determine if $f(x) = \lceil x/2 \rceil$ is $O(x)$. I know that this is true, and the textbook answer is: $|\lceil x/2\rceil|\leq |(x/2)+1| \leq C|x|$ for all $x > 2$, with ...
11 views

### Summation with Floor and Square Root functions + Tight Bounds

I was applying a methodology that allows to come up with iterative algorithms time-complexity function's closed-form. I ran into a particular where I ended up with the result below. I wouldn't have ...
18 views

### Necessary and/or sufficient conditions for summability of a sequence

It is clearly true that any $(a_n)_{n=1}^\infty$ that has $$a_n=O(n^{-1-\varepsilon}),$$ for some fixed $\varepsilon>0$, is absolutely summable: $$\sum\limits_{n=1}^\infty |a_n|<\infty.$$ My ...
20 views

31 views

37 views

### Asymptotics of incomplete Beta function $B_{1/2}(y+1,y)$ when $y\to\infty$

My question concerns the behavior of the incomplete Beta function $$B_{1/2}(y+1,y)=\int_0^{1/2}x^y (1-x)^{y-1}dx$$ in the large $y$ limit. I have been looking everywhere, but I can't find anything. ...
20 views

### Determining bounds for a sum with nested infinite series

I am computing the inner product of the characters of the trivial and the $k$-th irreducible two dimensional representations of the dihedral group $D_n$ of order $2 n$ when $n$ is even. The ...
22 views

25 views

### How to find the asymptotic expansion of $\int_{-\infty}^{y} e^{-x^2/2}/\sqrt{2\pi} dx$ where $x \in N(0,1)$?

I realize the function inside the integral is the pdf of a normally distributed random variable x, but am unsure how to use this to solve the problem. I am trying to relate it to the inverse of the ...
I am trying to prove the Weyl's asymptotic law for eigenvalues. In the document Weyl's law of p. $4$, I have managed to go up to the step $$\tilde{\nu_k} \leq \nu_k \leq \mu_k \leq \tilde{\mu}_k \... 1answer 17 views ### multiple of an integer and asymptotics Let us suppose that we have a positive integer N. We take the integer \lceil \log_2 N \rceil. Does there always exist an integer X \geq N such that the following both conditions are satisfied: ... 1answer 50 views ### When is 1-(1-p)^n \sim pn Let 0<p=p(n)<1 with p=o(1). For which p is it true that 1-(1-p)^n \sim pn? With \sim I mean that they are asymptotically the same, so \frac{1-(1-p)^n}{pn}\rightarrow 1, or at least ... 0answers 50 views ### How quickly can we find a value that has large multiplicative order modulo n? If we're trying to find an element modulo n that has multiplicative order at least \sqrt{n}, how quickly can we do this? We don't know if n is prime or composite, only that n definitely has a ... 2answers 37 views ### (x + y + xy)/2 = f( f^{[-1]}(x) + f^{[-1]}(y) ) Consider (x + y + xy)/2 = f( f^{[-1]}(x) + f^{[-1]}(y) ) Where f^{[-1}] denotes the functional inverse of f. How to find f ? How about the more General idea of finding f for a given g? ... 2answers 54 views ### Is there an way to calculate the value of O(n) [closed] Is there an way to calculate the value of O(n) (Big Oh)? I understand it's use in algorithm. But my question is how is the value calculated? 1answer 31 views ### Finding the Time Complexity in Big theta notation [closed] sum = 0 ; for ( i = 0 ; i < n ; i++ ) for ( j = 1 ; j < n^4 ; j = 4*j ) sum++; How would I go about finding the time complexity in ... 1answer 44 views ### Could Master Theorem be applied to this recurrence relation? I have the following recurrence relation T(n) = 4T(\frac{n+4}{2}) + n Is there some way in order to apply the Master Theorem to it? Or do I have to find an alternative approach in order to solve ... 0answers 33 views ### Upper bounding a sum of products Let a_k be an integer valued sequence, a_k \in \mathbb{N}^+ and let b_k = \#\{i: a_i=1,\; i \leq k\} and assume that b_k=o(k) (little o notation). How to prove that there exists a constant ... 0answers 23 views ### Asymptotic behavior of inverse laplace transform [duplicate] My question may be quite rough. Let F(\lambda) be the Laplace transform of some function f(t),$$ F(\lambda)= \int_0^\infty e^{-\lambda t}f(t) dt. $$If I have knowledge about F(\lambda)=O(\... 1answer 37 views ### Asymptotic lower bound of this function Suppose that n is an even number. Let$$f(n)=\frac{\sum_{j=1}^{n/2}\binom{n}{2j}\log(2j)}{2^{n-1}}.$$Can we find some function g(n) (e.g. \log(n) or n^\alpha) such that f(n)=\Omega(g(n))? ... 1answer 72 views ### Finding 8 co-primes \le 2^n We can find 8 co-prime integers \le 2^n for sufficiently large n. I'm looking for asymptotic bounds for the minimum distance away from 2^n we have to go before finding 8 co-primes. In other ... 1answer 22 views ### asymptotic notations : if 0<a<b then n^b=\Omega(n^a) If 0<a<b then n^b=\Omega(n^a). I have learned about this quiet recently and have come across this equation. I am having difficulty proving this. Any help would be appreciated. 2answers 73 views ### Help with a limit using big O? \lim_{x\to 0} \frac{4sin^{2}(\frac{x}{2})-x^{2}cos(\frac{x}{2})}{4x^{2}sin^{2}(\frac{x}{2})} is equal to \frac{1}{24} apparently but I can't work it out. My attempt: \lim_{x\to 0} \frac{4(\frac{... 1answer 56 views ### Does satisfy f(n)=\frac{\sigma(n)}{n^2} the hypothesis of Halasz’s inequality? Let \sigma(n)=\sum_{d\mid n}d the sum of divisor function. I would like to know if I can write an example of some of the following Theorem 1 or Theorem 2 from$$f(n)=\frac{\sigma(n)}{n^2}$$in Tao, ... 0answers 29 views ### Combinatorics of classifying objects. Given a multiset of n primes (with product of multiset less than 2^{n\log n}) how many ways can we assemble them into k composite number of equal size? I am looking for asymptotics. 2answers 61 views ### Testing convergence of series \sum_{n=1}^\infty\sin(\pi\sqrt{n^2+k^2}) [duplicate] Considering$$\sum_{n=1}^\infty\sin(\pi\sqrt{n^2+k^2}) depending on $k$, which can be real. I have absolutely no clue how to proceed. Tried to taylor it, but with no result.
$5 \log( \log n)$ $n (\log n)^2$ $\sqrt{n} \log n$ $n^{\frac{4}{3}}$ $n \log (\log n)$ $7 \sqrt{n}$ What is the ascending order of the growth function? Please give the explanation as well.