# Tagged Questions

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

558 views

### Big O Notation / landau symbols

I want to write these two in the big O notation: (it's $h\rightarrow0$) $f(h)=\sqrt{h^3}$ $f(h)=h\cdot \log h$ But I don't have any idea how to do this. Thanks for helping!
401 views

### Big O Proof by Contradiction

Question: Use a proof by contradiction to show that $5^n$ is not $O(3^n)$ NOTE: This is homework, please don't provide an answer, just want to know if I am on the right track. My Attempt: ...
38 views

75 views

### Density of Pythagorean triples

We define a Pythagorean triple as a triple $<a,b,c>$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$. In order to avoid duplicates, we say that a triple $<a,b,c>$ is legit iff $b>a$. ...
45 views

### Finding the product of a prime function…

If we take the primes $p_k < n$, and raise them to the highest power possible such that $(p_k)^{r_k} \le n$, what is the lower bounds on $\prod{ (p_k)^{r_k} }$? In other words, what are the ...
30 views

### Asymptotic behavior of a function defined via a complex integral

I would appreciate any comment/correction about what I did for the following problem, I would be very thankful if you let me know the parts of it which may not be very precise: Let $g(z)$ be defined ...
14 views

### Asymptotic Expansions of a Generalized Hyper-Geometric Function

Let $t>0,x>0$, and $$\{a_1,a_2,a_3\}=\{2, 2, 9/8 - (i t)/2\}$$ $$\{b_1,b_2,b_3,b_4\}=\{1, 1, 3/2, 17/8 - (i t)/2\}$$ We are looking for the asymptotic expansions of a generalized hyper-...
28 views

### An asymptotic numeric problem.

Given a large enough integer $N$ is there always a $c\in(0,1)$ such that $$(N+ N^{1-c}){c\ln(e N)}>\ln( N+( N)^{1-c})(N+2 N^c)$$ holds? What is this $c$ explicitly (at least a close approximation ...
37 views

28 views

281 views

### Asymptotic behaviour of sum over the inverse japanese symbol

I am interested in the asymptotic behavior of the sum $$\sum_{m=1}^M\frac{1}{\sqrt{m^2+\omega}}$$ for $1>\omega>0$ in the Limit $M\to\infty$ up to order $\mathcal{O}(M^{-1})$. The first thing I ...
25 views

### “Solving” for a sequence given an (expected) expression for the summation

Consider the "equation" $$\frac{1}{a_n}\sum_{k=1}^n ka_k = \mathcal{O}\left(\frac{n^2}{\log n}\right).\tag{1}\label{eq:conjec}$$ Does there exist some monotonically ...
29 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?
24 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 ...
37 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 ...
207 views

### Does $f(\epsilon)=o(\epsilon\ln(\epsilon))$ imply $\frac{f(\epsilon)}{\epsilon}=o(1)$?

I have the following homework question: Does $f(\epsilon)=o(\epsilon\ln(\epsilon))$ imply $\frac{f(\epsilon)}{\epsilon}=o(1)$ ? It doesn't seem correct to me, using the definition I could only ...
13 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 ...
25 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 ...
22 views

95 views

40 views

54 views

335 views

### Asymptotics for partitions of $n$ with largest part at most $k$ (or into at most $k$ parts)

Let $\bar p_k(n)$ be the number of partitions of $n$ with largest part at most $k$ (equivalently, into at most $k$ parts). Is there an elementary formula for the asymptotic behavior of $\bar p_k(n)$ ...
### Proving that $h=O(\log_2 n)$ if $h=\log_2 (n+1)$
Suppose that $h=\log_2 (n+1)$. Why is $h$ also $O(\log_2 n)$? I know the definition of big $O$ notation, and properties or logarithms, but I can't figure it out - that $+1$ is causing troubles.