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

learn more… | top users | synonyms (1)

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 ...
0
votes
1answer
222 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
2answers
51 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 ...
4
votes
1answer
460 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 ...
7
votes
1answer
98 views

Help proving $\sum_{n\le x}{\ln{n}}=x\ln{x}-x+O(\ln{x})$

Just learning a bit about big O notation and have come across this exercise. The notation used is $$\sum_{n\le x}{\ln{n}}=x\ln{x}-x+O(\ln{x})$$ and I am assuming that is equivalent to ...
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
2answers
54 views

Algorithm analyse with Big-Theta notation

Is $(n \log n) + \frac{\lfloor (\log n)^2\rfloor + \log n}{2} = \Theta(n \log n)$ ? My solution: $$ \begin{aligned} c_1 \cdot (n \log n) \le\,& (n \log n) + \frac{\lfloor(\log n)^2\rfloor + ...
0
votes
1answer
121 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
71 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 ...
2
votes
1answer
77 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
41 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
1answer
120 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: ...
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
79 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 ...
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 ...
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!
0
votes
1answer
60 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 $ ...
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
108 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 ...
4
votes
1answer
55 views

How to find the sum of Big-Oh's?

I will admit this is a homework problem, but I'm seriously stuck. I'm not looking for answers, but just any hints as to what to do next. Any tips would be appreciated. I am given: $$f_1(x) = ...
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
144 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
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 ...
0
votes
1answer
441 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
3answers
110 views

Recurrence $T(n) = T({2n\over5}) +n$ using Master Theorem

Solve the recurrence $$T(n) = T\left({2n\over5}\right) +n$$ My attempt: $a=1$,$\ b=\frac 52$, $f(n)=n$ For the most part I believe that is correct. Now I was wondering if my math is correct in ...
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· ...
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
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
139 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
139 views

Does the sum of reciprocals of the harmonic divisor numbers converge?

Does the sum of reciprocals of the harmonic divisor numbers converge? Define the following: Harmonic divisor number - $n$ such that $\sigma(n) \mid n\sigma_0(n)$. Equivalently, the harmonic mean of ...
6
votes
1answer
61 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 ...
0
votes
2answers
662 views

How does adding big O notations works

can someone please explain how adding big O works. i.e. $O(n^3)+O(n) = O(n^3)$ why does the answer turn out this way? is it because $O(n^3)$ dominates the whole expression thus the answer is still ...
0
votes
0answers
635 views

D ary tree node math

A d-ary tree is a rooted tree in which each node has at most d children (c) Suppose the tree has n nodes. What is the minimum the depth could possibly be, in terms of n and d? You can leave your ...
1
vote
1answer
84 views

base transformation rule significance in finding big o notation

Recall the equivalence: $$m=b^k \implies k = log_bm$$ as well as the base transformation rule: $$log_am=(log_ab)(log_bm)$$ Are the following true or false? (a) $log_2n$ is $O(log_3n)$ (b) ...
2
votes
4answers
1k views

Prove that $3^n$ is not $O(2^n)$

I have this question in my assignment. I need to prove, using only the definition of $O(\cdot)$, that $3^n$ is not $O(2^n)$. It is obviously true for any $n \geq 1$. To prove $3^n \in O(2^n)$, we ...
1
vote
2answers
189 views

Bounds for $T(n) = 2T(n/2) + n/\lg{n}$

I've been trying to find tight bounds for the equation: $$ T(n) = 2T(n/2) + n/\lg{n} $$ The master method does not apply since $n/\lg{n}$ is not polynomially smaller than $n$. So far I've found that ...
-1
votes
1answer
305 views

Logarithms and big O notation

Recall the equivalence: $$m=2^k \implies k=log_2m$$ (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 you can ...
0
votes
1answer
95 views

Big theta for a S(n)

Consider the following function: $$S(n)=1+c+c^2+⋅⋅⋅+c^n,$$ where c is a positive real number. (A) This function is the sum of a geometric series. Give a precise closed-form formula for S(n), interms ...
3
votes
1answer
89 views

Showing an approximation is uniformly asymptotic

I am trying to show that the approximation on $0\leq x \leq 1$ $$\phi(x,\epsilon) \sim \sin x+ \epsilon \cos x - \epsilon$$ is uniformly asymptotic to the exact solution $$f(x,\epsilon) = ...
7
votes
1answer
148 views

Approximate $\int_0^{\pi /2} \frac{ds}{\sqrt{1-x\sin^2s}}$

I am trying to approximate the following integral $$K(x)=\int\limits_0^{\pi /2} \frac{ds}{\sqrt{1-x\sin^2s}}$$ with $0<x<1$. I need to show that for x close to one that $K(x)\sim ...
1
vote
1answer
185 views

Why does $af(n/b) <= cf(n)$ for $c < 1$ imply that $f(n) = \Omega(n^{\log_ba+\epsilon})$?

The Master method for solving recurrences of the kind $T(n) = aT(n/b) + f(n)$ has a third case, which requires a regularity condition to hold: $$ af(n/b) \le cf(n) \qquad a \ge 1, b > 1, c < ...
0
votes
2answers
1k views

Big O notation for summation

Consider the summation $$S(n)=1^c+2^c+3^c+...+n^c,$$ where c is some fixed positive integer. (a) Show that $S(n)$ is $O(n^{c+1})$ I did this part the following way, $S(n)$ is $O(n^{c+1})$ because ...
2
votes
2answers
353 views

Big O and Omega Properties

I am trying to think of a case where this is not true: $f(n) = O(g(n))$ and $f(n) \neq \Omega(g(n))$, does $f(n) = o(g(n))$? I suspect that it has to do with the varying $c$ and $n_{0}$ constants ...
0
votes
1answer
267 views

Does log $f(n) = O($log $g(n))$ imply $f(n) = O(g(n))?$

Assuming log is base 2, if I know that: log $f(n) = O($log $g(n))$. Does this imply that $f(n) = O(g(n))$? I understand that the converse is true.
0
votes
1answer
72 views

Time Complexity involving a conditional f(n) when n is even and odd

Trying to find an asymptotic relationship between: $f(n)$ and $n^2$ where $f(n)$: if n is even, $f(n) = 8n$. if n is odd, $f(n) = 5.5n^2$. Not sure how to approach when the function is ...
2
votes
1answer
57 views

Comparing time complexities

I'm trying to understand which of the following functions is strictly faster growing ($\Omega$, $o$-notation or $\theta$-notation). Not sure how to approach the following equations: $$\bf{n^{0.3} \ ...
0
votes
1answer
962 views

Geometric series and big theta

Consider the following function: $$S(n)=1+ c + c^2 + ··· + c^n,$$ where c is a positive real number. (A) This function is the sum of a geometric series. Give a precise closed-form formula for ...
1
vote
1answer
123 views

GCD = 1 and harmonic numbers, what is the exact asymptotic?

I am looking for the exact asymptotic for this partial sum: $$a(N) = \sum_{n=1}^{n=N}\sum_{k=1}_{GCD(n,k)=1}^{k=n*m} \frac{1}{k}$$ where $m$ is some integer $1,2,3,4,5,...$ My guess was that since ...