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
28 views

Approximating the modulus of a Complex Function near a point.

Let $\Omega$ be a domain in $\mathbb{C}$, and let $z_0 \in \Omega$. Let $f$ be analytic on $\Omega$. Let $z=z_0+re^{i\theta}$ for $r$ small. Assume that $f(z_0) \neq 0$ and $f'(z_0) \neq 0$. I want ...
0
votes
1answer
33 views

Big-O evaluation:

I have the expression: $$f_{k}(n,m) = (n - k)(m - k) + f_{k+1}(n,m)$$ which runs until k = n or m. What is the big theta of this function in terms of n,m? A naive approach is to assume that m does ...
3
votes
1answer
184 views

Asymptotics for sums involving factorials

This question is rather general, but I have recently encountered the following situation in a variety of different settings. Let us suppose that we are given a complicated sum involving factorials ...
1
vote
3answers
409 views

What is the order of the sum of log x?

Let $$f(n)=\sum_{x=1}^n\log(x)$$ What is $O(f(n))$? I know how to deal with sums of powers of $x$. But how to solve for a sum of logs?
5
votes
1answer
152 views

Find asymptotic for $s(n)=\min\{m\in{\mathbb N}\mid C_n^m\cdot e^{-m^3/(\ln m)^{10}}<1\}$

I have some strange function: $s(n)=\min\{m\in {\mathbb N} \mid C_n^m\cdot e^{-m^3/(\ln m)^{10}}<1\}$ and I need to find asymptotics for it. I have a solution for this except one last step, I ...
0
votes
1answer
47 views

Proving that if $f$ is equal to $g$ asymtotically then their distance tends to zero

How could I prove via limit definition that from $$ \lim_{n \to \infty} \frac{f(n)}{g(n)} = 1 $$ derives $$ \left| f(n) - g(n) \right| \to 0 $$ ? Previous attempt took me to $$ \left| f(n) - g(n) ...
5
votes
6answers
289 views

Asymptotic solution to the integral $\int_{-\pi/2}^{\pi/2} (\alpha + \sin x)^n \cos^2 x\,\mathrm{d}x$

Recently, I have posted a question on how to find a reduction formula for the trigonometric integral $$\int (\alpha + \sin x)^n \cos^2 x\,\mathrm{d}x.$$ This problem seems to be tough, however. When ...
5
votes
2answers
201 views

Find asymptotics of $x(n)$, if $n = x^{x!}$

Find the asymptotic for $x(n)$, if $n = x^{x!}$. I've tried 1) to take a logarithm: $x! \log{x} = \log{n}$. 2) to find $n'(x)$, using gamma-function for factorial $\Gamma(z) = \int_0^\infty ...
1
vote
1answer
50 views

Proof that $n^2 \not\in \omega(2^n)$

I'm trying to prove that $n^2 \not\in \omega(2^n)$ and I have to do it from definition. $f(n) \in \omega(g(n)) = \left\{f(n)| \forall c>0, c \in \mathbb{R}, \exists n_0 \in \mathbb{N}, \forall n ...
1
vote
1answer
46 views

getting T(n) when I get bigTheta complexity from recurrence relation

I wonder how could I solve the recurrence relation when I calculate complexities. Let me explain it via an example: $T(n)=2T(n/2) +n$. Solve this recurrence relation. I know from the Master theorem ...
1
vote
3answers
849 views

Show that $(n + a)^{b}$ = $\Theta(n^{b})$

In the book I'm following I got the following solution: To show that $(n + a)^b = \Theta(n^b)$, we want to find constants $c_1, c_2, n_0 > 0$ such that $$0 \leq c_1 n^b \leq (n + a)^b \leq c_2 ...
1
vote
1answer
184 views

running time of a multiplication algorithm

Here is a multiplication algorithm: given inputs x and y, add x to itself y - 1 times: z = 0 while y > 0: z = z + x y = y - 1 return z What is the running time of this algorithm? Is it ...
0
votes
1answer
58 views

consider the following subroutine, what is the running time

Suppose A(.) is a subroutine that takes as input a number in binary, and takes time O($n^2$), where n is the length (in bits) of the number. (a) Consider the following piece of code, which starts ...
1
vote
2answers
65 views

big Oh notation of the smallest k

Recall the equivalence: $$m = 2^k , k = \log_2 m$$ (a) Consider the sequence: $$a_1 = 1; a_{k+1} = 2a_k$$ What is the smallest $k$ for which $a_k \geq n$? Your answer should be a function of $n$, and ...
14
votes
3answers
481 views

Can a function “grow too fast” to be real analytic?

Does there exist a continuous function $\: f : \mathbf{R} \to \mathbf{R} \:$ such that for all real analytic functions $\: g : \mathbf{R} \to \mathbf{R} \:$, for all real numbers $x$, there exists ...
1
vote
1answer
228 views

Calculating expected value of distance in a circle-circle intersection

Consider two circles $c_1$ and $c_2$ both of radius $r$ located in 2-D plane such that the distance between their centers is $r$. Assume a point is randomly and uniformly chosen within their ...
2
votes
3answers
214 views

how does the n-bit number related to big O notation

in algorithms you frequently have to evaluate problems like this, Let $x$ be an $n$-bit integer. For each of the following questions, give your answer as a function of $n$. my question is simple, ...
1
vote
2answers
161 views

Solving the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2}\log(n)$

Please help me solve the recurrence $$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2}\log(n) $$
0
votes
2answers
70 views

Meaning of $O(n)$ in an expression

As my mathematical knowledge is increasing, I have been seeing more and more of $O(n)$ implementation in expressions. Here is what I mean. Example: $$z^{q_{N+1} + q_N} w^{q_{N+1} + q_N} (-1)^N (w-1)/w ...
0
votes
1answer
270 views

How can I tell/compare the asymptotic complexity of a function?

For something, like a quadratic I just take the highest degree and see if it is theta or big O or Omega of n, correct? So like 2n^2+2n+1 could be theta(n^2). What are the general ...
0
votes
1answer
153 views

big-O proof with power functions

I was wondering if anyone could show a proof for why $a^x$ is $\mathcal{O}(b^x)$ if $a$ and $b$ are constants and $a < b$. In other words, with power functions, does the function with the largest ...
0
votes
1answer
28 views

How is this result obtained?

I am reading a paper, and having a hard time determining how a result was obtained. The paper states that: Since the total number of linear-extensions is initially $n!$ and probing an edge reduces the ...
4
votes
1answer
500 views

How to analyze the asymptotic behaviour of this integral function?

Based on the asymptotic analysis of correlation functions at large distence in Physics, now I get a math question. Let the function $$f(x)=\int_{-1}^{1}\sqrt{1-k^2}e^{ikx}dk.$$ Without working out ...
0
votes
2answers
53 views

What does $\text{poly}$ stand for in $O(\log^{10.5}n \cdot \text{poly}(\log \log n))$?

I posted this question on cstheory and found that "poly(f(n))" is shorthand for "polynomial in f(n)" or $f(n)^{O(1)}$, hence poly(log log n) is shorthand for $(log log n)^{O(1)}$. However, I don't ...
0
votes
1answer
125 views

Threshold of connectivity in a random graph

I am trying to understand the proof to a random graph problem (the threshold for connectivity of $G \sim G(n,p)$ being $\frac{logn}{n}$). I am struggling to see exactly why the following holds: ...
1
vote
1answer
22 views

Using $\lim_{x \to \infty}$ to determine whether $f(x) = \Theta(g(x))$?

I'm learning it in the context of Running time complexity. to determine whether $f(x) = O(g(x))$, you can check whether the folloing limit:$$\lim_{x \to \infty} {f(x) \over g(x)} < \infty$$ if ...
0
votes
1answer
136 views

Which form of Euler-Maclaurin formula to use?

This question may be rather elementary, but I am sort of confused about various forms of the Euler-Maclaurin summation formula and their use. For instance, let us suppose that we want to approximate ...
1
vote
0answers
74 views

How to analyze the asymptotic properties of this function?

Let the function $$f(\mathbf{r})=\int_{\Omega }e^{i\mathbf{k} \cdot \mathbf{r}}d^2\mathbf{k}$$, where $\mathbf{k} ,\mathbf{r}\in\mathbb{R}^2$, and $\Omega \subset \mathbb{R}^2$ is some finite region ...
3
votes
1answer
86 views

Asymptotics of sequence depending on Tricomi's function

I'm dealing with the following sequence $$ p_n = U(a, a - n, 1)$$ where $a > 0$ and $U$ is Tricomi's function. I suspect that asymptotically when $n \to \infty$ its behaviour is a power law ...
2
votes
1answer
78 views

What is the asymptote for the positions of the largest Stirling numbers of the second kind?

The infinite lower triangular array of Stirling numbers of the second kind starts: $$\begin{array}{llllllll} 1 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} ...
0
votes
1answer
42 views

Is there a closed form for…

I was working on an analysis question, and was wondering if there's a closed form for $\sum_{i=0}^{log(n)}(1/2^i)log(i)$? Unless I have made a mistake, I am trying to show that ...
0
votes
0answers
34 views

Asymptotics for a recurrence relation

Here we have $T(1)=1$ and $$T(n)=T(n-1)+T\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n.$$ How to show its asymptotics? I suppose it's $n^{\Theta(\log n)}$, but not sure. For the question here, ...
0
votes
1answer
81 views

Question about Big-O notation

I'm learning Big-O notation in school and my friend and I have a hard time understanding some parts of it and we don't agree on some answers in the exercises. There are two cases on which we don't ...
1
vote
1answer
32 views

Asymptotic behaviour of a function of a bivariate normal vector

Let $(Z_1,Z_2)$ be a bivariate standard normal vector and $x\in\mathbb{R}$. We consider $$f(\sigma_l):=\left| \operatorname{E}[1\{Z_1\leq x/\sigma_l\}1\{Z_2\leq ...
0
votes
1answer
15 views

Asymptotics of a real sequence

Let $(a_n)_{n\in\mathbb{N}}$ be a real sequence with $a_n\in O(n^d)$ $(d\in (-1,0))$. Now we consider the expression $$ b_n:=(1-\sqrt{1-a_n}).$$ Is $b_n\in O(\sqrt{n^d})$? Thanks!
6
votes
1answer
63 views

Asymptotic behaviour of sum of decreasing definite integrals

I would like to calculate: \begin{equation*}g(K, T) = \displaystyle \sum_{k=1}^{K} \sum_{t = 1}^{T} \int_{0}^{1} \left(1 - z^k\right)^t \, dz. \end{equation*} If no closed form solution exists, I ...
8
votes
3answers
471 views

the following inequality is true, but I can't prove it

The inequality $$\sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right)$$ holds for all integer $d\geq 1$. I use computer to verify it for $d\leq 50$, and find ...
0
votes
1answer
61 views

Given $ h(x)=f(x)+O(g(x)) $ estimate using asymptotic notation $\frac{1}{h(x)}$

Given $ h(x)=f(x)+O(g(x)) $ and knowing that $ \lim_{x \to \infty}=\frac{g(x)}{f(x)}=0$ (int other words $f(x)=o(g(x))$) find such F(x) and G(x), $\frac{1}{h(x)}=F(x)+O(G(x)) $. Because $ ...
1
vote
1answer
63 views

Prove that $\log_2 n$ is not bounded polynomially from below, need 2nd step

i.e. that $\log_2 n\not\in\Theta(n^x)$ for any $x > 0$ i shall not use induction on $x$ ( as $x = 1$ base case etc) my guess is : i use the def. of big theta: $$ 0≤c_1·n^x \le \log_2 n \le c_2· ...
2
votes
0answers
31 views

Is there a 2D 3-colorstate mobile automaton that grows like $ln^{0,5}(t)$?

Define an integer function $f(t)$ for an integer $t>25$ such that $|f(f(t)) - ln(t)| < \sqrt {ln(t)}+2$. Define $L(X(t))$ as the number of nonwhite states at iteration $t$ of mobile automaton ...
1
vote
1answer
113 views

Relationship Little '$\mathcal{o}$' and Big '$\mathcal{O}$'

I'm learning about asymptotic analysis and, as a starting point, big and little o definitions. On the Wikipedia page, http://en.wikipedia.org/wiki/Big_O_notation further down under the heading for ...
0
votes
2answers
51 views

Hard Asymptotic anyalsis problem from a text book

Hi can anyone tell firstly what the difference is between asymptotic anylasis and taking limits? Can anyone help me with this problem. $$\lim_{x \rightarrow \infty} (xy-x) $$
1
vote
0answers
151 views

Questions about the superfactorial function.

N superfactorial or $n\$$ is defined as - $$n\$=\prod_{k=1}^n k!$$ Then is there any asymptotic formula for this? Are there any infinite series , integrals related to this function? Is there a ...
0
votes
1answer
33 views

Asymptotic behaviour of real sequences

Let's say we have two real sequences $(a_n)_{n\in\mathbb{N}}$ and $(c_n)_{n\in\mathbb{N}}$ with $c_n\in o(\frac1n)$ (i.e. $c_n(\frac1n)^{-1}\xrightarrow{n\rightarrow\infty}0$). And for all ...
0
votes
1answer
517 views

Prove that Big O (lg n) is a subset of Big O(sqrt(n))…

Prove that Big O (lg n) is a subset of Big O(sqrt(n)) and exists an element x in set Big O(sqrt(n)) that is not in Big O(lg n). This is a home work question and I have no clue where to start. Do I use ...
0
votes
1answer
23 views

What is $O(\sqrt{2^n}n^2)$?

What is $O(\sqrt{2^n}n^2)$? Is it $O(2^n)$, or does the square root cause it to be reduced? I'm trying to analyze an algorithm that I came up with, and if it still has exponential time cost, I'm ...
3
votes
1answer
3k views

Big O estimate of simple while loop

Give a big-O estimate for the number of operations, where an operation is an addition or a multiplication, used in this segment of an algorithm (ignoring comparisons used to test the conditions in the ...
0
votes
1answer
148 views

How to determine a $\Theta$-class of a Function

I have 6 functions that I have to determine which of 4 given $\Theta$-classes or neither of them. Example of a function I have been given: \begin{align*} \textit{$f_1$}(n) =&(17\textit{n}+1) \\ ...
0
votes
1answer
29 views

Show $5 \cdot 4^{\log_{2}{n}}$ is $\Theta(n^{2})$.

I'm having trouble working out the algebra for this problem. I know that we need to show $\exists c$ s.t. $5 \cdot 4^{\log_{2}{n}} \leq c \cdot n^{2} \forall n \geq n_{0}$, and also the other ...
0
votes
1answer
106 views

Showing a recurrence is $\Theta$(n)

Specifically how do you go about showing that $$ 2T(n/2)+1 =\Theta(n) $$ Not looking for an answer, as much as the process? I'm studying for a test and this is one of the review problems. Thanks in ...