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

learn more… | top users | synonyms (1)

2
votes
2answers
217 views

How to show that a “Big-Oh” set is a subset of another?

Let's say we have two "Big-Oh" sets called $\text{Constant}$ and $\text{Logarithmic}$, such that one has $O(1)$, and the other has $O\big(\log(n)\big)$, respectively, how would I show that ...
2
votes
2answers
128 views

Show that $f \in \Theta(g)$, where $f(n) = n$ and $g(n) = n + 1/n$

I am a total beginner with the big theta notation. I need find a way to show that $f \in \Theta(g)$, where $f(n) = n$, $g(n) = n + 1/n$, and that $f, g : Z^+ \rightarrow R$. What confuses me with this ...
15
votes
3answers
996 views

How do you prove that $n^n$ is $O(n!^2)$?

It seems obvious that: $$n^n \in O(n!^2)$$ But I can't seem to find a good way to prove it.
5
votes
1answer
170 views

Asymptotic formula for $k$-partitions of a number

Asymptotic formula for all the partitions of a number is given by $$p(n) \sim \frac{1}{4n\sqrt{3}} e^{\pi \sqrt{\frac{2n}{3}}}$$ Only fraction of those will be $k$-partitions. What is asymptotic ...
1
vote
2answers
83 views

what is the meaning of $a_n$ grows as for example $O(n\log n)$ or $O(n^2)$

Given a positive and increasing sequence $\{a_n\}$, what is the meaning of $a_n$ grows as for example $O(n\log n)$ or $O(n^2)$. I have read this in some books but the google search did not yield ...
0
votes
1answer
132 views

Does $f \sim g$ imply $f \asymp g$ in certain conditions?

I got a good answer to this question over on MathOverflow a while ago. Harald Hanche-Olsen claimed that, if $f, g: D\to \mathbb{R}^+$, then $$ f(x) \sim g(x) \implies f(x) \asymp g(x) \qquad \qquad ...
1
vote
1answer
110 views

Understanding a simplification in a theorem

I'm trying to understand a theorem in a paper on page 14/24. We are given that $$Z = (nq-1) \log \left(\frac{M+nq-1}{nq-1} \right) + M \log \left(\frac{M+nq-1}{M} \right) + \frac{1}{2} \log \left( ...
2
votes
0answers
196 views

Asymptotic bounds for a sum

I have this sum, which probably doesn't exist in closed form. $$\displaystyle ...
1
vote
1answer
60 views

Comparison of the order of two functions

This is along the lines of Problem 9.8. in 'Concrete Mathematics' by Graham, Knuth and Patashnik. Does any of the relation $\prec$, $\succ$ or $\sim$ exist between functions $f(n) =\displaystyle ...
1
vote
1answer
137 views

Does there exists a absolute measure for growth-rate of a function?

In computer science there are many notions of growth-rate of a function. These notions are, however, always relative in the sense that growth-rate of some function $f$ is always relative to some other ...
3
votes
1answer
95 views

Discovering Appropriate Bounds in Multivariable Asymptotics

I am having some difficulty with multivariable asymptotics. Let me provide a concrete example of the kind of thing I mean. Stirling's approximation for $n!$ is $$ n! \sim \sqrt{2 \pi n}\left( ...
1
vote
3answers
191 views

better understanding of incomplete gamma function $\Gamma(0,x)$

By definition incomplete Gamma function is:$$\Gamma(0,x)=\int_{x}^{\infty}t^{-1}e^{-t}dt $$ I have an expression which includes $$\Gamma(0,r(A)e^{i\phi(A)}),$$ where $A>0$ is a parameter, and ...
3
votes
1answer
229 views

Manipulating Equations with Big-oh

Note: first part is all context to question labeled "The Question" below: Working through the CLRS Introduction to Algorithms, 3rd ed, in Chapter 6.4 as they are talking about heaps they state: ...
3
votes
1answer
724 views

Determine if function is little-o, little-omega or big-theta

Let $f(n) = n^3(5+2\cos(2n))$ and $g(n) = 3n^2+4n^3+5n$. Given these two functions, I must determine the appropriate symbol where the underscore is: $f(n) \in \_(g(n))$ So, first thing to do is take ...
0
votes
1answer
91 views

Excercise: Ordering functions using the BigO notation

This was one of the previous year's exam questions. I have to order the following functions according to their growth rates using the $\mathcal O(n)$ notation. $f_1(n) = 2010 * \log_3(n^n)$ $f_2(n) ...
5
votes
1answer
109 views

For which x does $\sum\limits_{i=0}^{n}x^i=O(n)$ hold?

I'm stuck with this exercise: I have to find for which $x$ the estimate $\displaystyle\sum\limits_{i=0}^{n}x^i=O(n)$ holds. It seems intuitive to me that this must be the case for all $x \in (0,1)$ ...
4
votes
2answers
297 views

Is this the normal big-O?

My book on quantum mechanics introduces the notation $\mathcal O(1)$ as follows: We represent it by the formula $\Delta x \Delta k \gtrsim \mathcal O(1)$ where $\Delta x$ and $\Delta k$ are the ...
2
votes
2answers
650 views

Omitting bases in Logs -> Big O

Can anyone explain, with the aid of a mathematical proof, why bases are omitted in Big - O notation? EDIT: I don't understand how: NB: $\log_2(n) =$ log to the base 2 of n $log_2(n) = ...
1
vote
1answer
2k views

asymptotically larger vs polynomially larger

What is the difference between x being asymptotically larger than y and x being polynomially larger than y?
7
votes
1answer
91 views

Asymptotic Behavior of Iterated Sums

Given the integral identity \begin{align} \int_{0}^{t} \cdots \int_{0}^{t - t_{1} - \dots - t_{n -1}} 1 \ dt_1 \cdots dt_n = \frac{t^{n}}{n!}, \end{align} I believe it is true that \begin{align} ...
7
votes
1answer
251 views

Stochastic assignment problem

Given an $n \times n$ real matrix $C$, we can try to maximize $$\Phi(C, \pi) = \frac{1}{n} \sum_{i} C_{i,\pi(i)} $$ over $\pi \in S_n$, the set of all permutations on $n$ objects. What can one say ...
0
votes
1answer
338 views

Big O Rule Proof

Give a mathematical definition of the order notation $f(n) \in \mathcal O(g(n))$ and explain how this concept relates to the algorithmic idea of worst case analvsis. How do I go about answering ...
0
votes
2answers
158 views

Asymptotic probability: boys and girls in a line

We have $n$ people: $\alpha n$ are boys and $(1-\alpha)n$ are girls. They are standing in a line in a random order. We pick up one boy also at random. What can one say about the probability that ...
1
vote
3answers
343 views

Big Oh Question

I have the following question: Is the following statement true or false? ** All logs to base 2 log2n is a memeber of O(log(n)) My attempt: log2n - clogn <= 0 log2 + logn - clogn <= 0 1 + ...
4
votes
2answers
237 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)$ ...
6
votes
1answer
262 views

Algorithmic Analysis Simplified under Big O

Hi I am revising for my exams and I have the following inhomogeneous first order recurrence relation defined as follows: f(0) = 2 f(n) = 6f(n-1) - 5, n > 0 I ...
6
votes
1answer
263 views

Fewest required values in magic square?

A magic square of order $n$ is an $n \times n$ grid containing each of the numbers $1,2,\dots,n^2$, so that the numbers in each row, column, and diagonal sum to the same number $n(n^2+1)/2$. This ...
5
votes
2answers
177 views

An Alternate Proof to a Theorem Involving “e”

In a paper, it was claimed that $\lim_{x \to \infty} (1-\frac{f(x)}{x})^x \sim e^{-f(x)}$ when $\frac{(f(x))^2}{x}$ is $o(1)$. I proved the claim in the following way; however, I'm seeking a simpler ...
23
votes
2answers
763 views

How to show that $\sum\limits_{k=1}^{n-1}\frac{k!k^{n-k}}{n!}$ is asymptotically $\sqrt{\frac{\pi n}{2}}$?

According to "Concrete Mathematics" on page 434, elementary asymptotic methods show that $\displaystyle \sum_{k=1}^{n-1}\frac{k! \; k^{n-k}}{n!}$ is asymptotically $\sqrt{\frac{\pi n}{2}}$. Does ...
3
votes
0answers
186 views

proving the saddle point method in a specific case

$1:$ the problem Let $f : U \to \Bbb{C}$ be analytic on some open set $U$ that includes the closed unit ball. Define a path $\gamma$ by: $\gamma(t) = e^{i t}$, -$\pi < t \leq \pi$ I want to ...
10
votes
3answers
531 views

How does Lambert's W behave near ∞?

How does $W$ behave near $+\infty$ compared to $\log$? In particular, I'm interested in the asymptotic expansion of $$\frac{W(x)}{\ln(x)}$$ near $\infty$ (but along the positive real line, if that ...
4
votes
2answers
145 views

Basic question about natural density

Suppose that we have a sequence of finite sets $A_1, A_2, \ldots$, which partition $\mathbb{N}$. I am making no other assumptions on the $A_n$ - i.e. there could be any amount of interleaving between ...
1
vote
1answer
184 views

Do equal mean and equal moment imply equal distribution?

If two sequences $\{a_k\}$ and $\{b_k\}$ are such that $$\lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}(a_k-b_k)=0$$ $$\lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}(a_k^2-b_k^2)=0$$ does it mean that ...
1
vote
3answers
1k views

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer, need help, I dont know how to solve it?
3
votes
2answers
587 views

Proving the bound on a recurrence relation

I am trying to prove the recurrence $2T(n-1) + 1$ has the bound $\theta(2^{n})$. $T(1) = \theta (1)$ My attempted solution: \begin{align*} T(n) &= 2T(n-1) + 1 \\ &= 2 \{ 2T(n-2) + 1 \} + 1 ...
6
votes
1answer
155 views

Inequality on balls/bins with nested logs

Let $k = \lceil \frac{3 \ln n}{\ln \ln n}\rceil$. How does one show that $$ \left(\frac{e}{k}\right)^k \frac{1}{1-\frac{e}{k}} \le n^{-2} ? $$ This is from p. 44 of Motwani and Raghavan, Randomized ...
5
votes
2answers
361 views

Big $O$ vs Big $\Theta$

I am aware of the big theta notation $f = \Theta(g)$ if and only if there are positive constants $A, B$ and $x_0 > 0$ such that for all $x > x_0$ we have $$ A|g(x)| \leq |f(x)| \leq B |g(x)|. ...
4
votes
2answers
897 views

Big-O Notation and Asymptotics

I realize that this is not a typical programing question but its still related. If anyone could help me out I would really appreciate it because I have a midterm coming up and this is the part that I ...
7
votes
2answers
741 views

How to Use Big O Notation

In my question about the convergence/divergence of $$ \sum_{n=2}^\infty \frac{1\cdot 3\cdot 5\cdot 7\cdots (2n-3)}{2^nn!}. $$ here: Why Doesn't This Series Converge? Zarrax gave the answer: ...
2
votes
1answer
849 views

How to prove asymptotic property with big O notation?

Could you help me to show: $g(x,\epsilon)+f(x,\epsilon)=O(|\phi(x,\epsilon)|+|\psi(x,\epsilon)|)$ but $g(x,\epsilon)+f(x,\epsilon)\neq O(\phi(x,\epsilon)+\psi(x,\epsilon))$ (both when ...
8
votes
1answer
5k views

Quicksort Running Time

I am trying to refresh my knowledge (and hopefully learn more) about Algorithm Analysis. I took a course on this two years ago but I am trying to catch up on what I had learned back then. The way I ...
1
vote
1answer
101 views

More help with vertical asymptotes

Of the six questions regarding finding vertical asymptotes of graphs, I've had problems with two. The second is using the graph of $$g(x)= \frac{3+x}{x^{2}(3-x)}$$ Now, looking at the function, it ...
3
votes
3answers
433 views

Find the vertical asymptote of a function

For an assignment, I was asked to find the vertical asymptote of the function $$g(x)= \frac{\frac{1}{2}x^3-4x^2+6x}{7x^2-56x+84}.$$ According to my text, a reliable method of finding the asymptote is ...
0
votes
1answer
228 views

Notation: What does $f(x) = x^{-\omega(1)}$ mean?

I am reading a cryptography paper, and the authors introduce a function $f(x) = x^{-\omega(1)}$ and call it a negligible function in $x$. What is the possible meaning of this?
0
votes
2answers
165 views

how many bits to write $\sqrt x $?

x is an integer, and i can write it with $\log_2 x$ bit, and, viceversa, with $n$ bit i can write a number till $2^n$.. but.. how many bits to write $\sqrt x$ ? EDIT: the integer part!
5
votes
3answers
727 views

How to solve $n < 2^{n/8}$ for $n$?

This is from an exercise (1.2.2) in introduction to algorithms that I'm working on privately. To find at what point a $n \lg n$ function will run faster than a $n^2$ function I need to figure out for ...
0
votes
5answers
501 views

How to evaluate $\displaystyle\sum_{i=1}^{n/2}1$

I am trying to measure complexity of the following code segment int sum = 0; for (int i = 1; i <= n/2; i++) { sum++; } As far as I understand it can be ...
4
votes
1answer
336 views

Geometric / Visual explanation that the average height of a random binary tree of given size $n$ is asymptotically $2\sqrt{\pi n}$

I just finished reading the proof that the average height of a random binary of given size $n$ is asymptotically $2\sqrt{\pi n}$. I'm now searching for an intuitive, or geometric, or visual proof of ...
5
votes
3answers
665 views

how to solve $T (n) = T \left(\frac{n}{2} +\sqrt{n}\right) +\sqrt{6046}$

How can I solve the recurrence $$T (n) = T \left(\frac{n}{2} +\sqrt{n}\right) +\sqrt{6046}\ ?$$ Please don't just write the name of the method, as I just started learning this stuff and things are a ...
2
votes
3answers
219 views

stuck with master method

$$T (n) = 3T (n/5) + \log^2 n$$ i am trying to solve this recurrence i have been told that it is master methods case 1 but how do i compare $\log^2n$ with $n^ {\log_5 3}$