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

little-o and 3 functions

If we have 3 function $f$, $g$ and $h$ such that : $f$ is not $o(g)$ $f$ is $o(h)$ Can we conclude that $g$ is $o(h)$ ? i.e is the following true ? $lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} ...
1
vote
1answer
45 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 ...
5
votes
2answers
194 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 ...
3
votes
1answer
175 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
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
183 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 ...
0
votes
2answers
42 views

how long does this subroutine and loop take

Suppose A(.) is a subroutine that takes as input a number in binary, and takes linear time (that is, O(n), where n is the length (in bits) of the number). Consider the following piece of code, which ...
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 ...
2
votes
1answer
61 views

I have a Big-O Problem

I want to show: $(1-3z)^{3/2}$ is O(1-3z) as $z\rightarrow 1/3$ where $z \in \mathbb{C}$ I would like to be able to write: $\displaystyle \frac{(1-3z)^{3/2}}{1-3z}=(1-3z)^{1/2}$, and then show that ...
2
votes
3answers
211 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
159 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) $$
1
vote
1answer
216 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 ...
0
votes
1answer
99 views

Conditions for $o(|u|^{-1})$ decay of the Fourier transform of a bounded variation function

As the question suggests I am looking for a (not very restrictive) condition on a function of bounded variation so that its Fourier transform is $o(|u|^{-1})$ as $|u| \to \infty$. Let me elaborate on ...
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 ...
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
141 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 ...
0
votes
1answer
234 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
484 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
126 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
73 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
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
1answer
123 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
80 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
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 $ ...
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
145 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
484 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
112 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
141 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
144 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
62 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 ...