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
2answers
67 views

Probability that colored balls are separated

Say we throw $b$ blue balls and $r$ red balls uniformly into $n$ boxes. The probability that no box contains a red as well as a blue ball is then, by the inclusion exclusion principle: $$p = \sum_{k,\...
1
vote
1answer
35 views

Growth Rates of F(n) vs. F(n) + F(n-1) + … F(1)

I am trying to understand growth rates between a function and its sum recursively. For example I understand that if: $F(n) = n$ Then the sum $n + (n - 1) + ... 2 + 1 = \frac{n(n-1)}{2}$ which is $O(...
1
vote
0answers
215 views

Algorithm for matrix addition and multiplication

Let $m$, $n$ be integers such that $0 \leq m,n < N$. Define: Algorithm A: Computes $m + n$ in time $O(A(N))$ Algorithm B: Computes $m \cdot n$ in time $O(B(N))$ Algorithm C: Computes $m\bmod n$ ...
0
votes
2answers
89 views

Please provide additional information for a Big-O problem solution

I am studying a Big-O example but I just do not get the idea. I have already seen that this question was asked in this forum but I am still confused. Can someone please provide another explanation so ...
1
vote
1answer
76 views

Why do O(logn) & O(exp(n)) Have Polynomial & Non-Polynomial Running Time Complexities Respectively Despite Their Taylor Series?

I understand that a function, say $f(x)$, belongs to a class $O(g(x))$ iff: $$ \exists k > 0 \ \ \exists \ \forall n > n_0: |f(n)| \leq |g(n) \cdot k| $$ I also know that $log(x)$ is has ...
0
votes
0answers
39 views

About growth rate of function

Suppose the function $ d(T)→\infty $as $ T→∞ $, what is the appropriate growth rate of $ d(T) $ in order that $ d(T)^{2d(T)-1}/T^c→0 $ with $c$ being a constant? Thanks very much for your kind help.
1
vote
1answer
47 views

limiting variances of iid sample mean

In the book Statistical Inference (George Casella 2nd ed.), page 470, there is an example: $\bar{X}_n$ is the mean of $n$ iid observations, and E$X=\mu$, $\operatorname{Var}X=\sigma^2$. "If we take $...
0
votes
3answers
64 views

Showing that $4n + 3n \log_2n$ is $O(n\log_2n)$

I need to prove that: $$ 4n+3n\log_2n \text{ is } O(n\log_2n) $$ How can I find $c$ and $n_0$ for $3n\log_2n$? Also, using the big-Oh definition, I need to show that: If $g_1(n)$ is $O(f(n))$ and $...
1
vote
1answer
20 views

Is the integral finite if the integrand is $o(x^{-1})$?

According to theorem 2.2 in this file http://www.stat.umn.edu/geyer/old06/5101/notes/n1.pdf If $\lim_{x\to\infty} \frac{g(x)}{x^{-1}} =0$, nothing can be said about the existence of $\int_a^\...
0
votes
1answer
135 views

How do I determine a percentage increase of a function caused by increasing the input?

Suppose you have algorithms with the five running times listed below. (Assume these are the exact running times.) How much slower do each of these algorithms get when you (a) double the input size, or ...
2
votes
2answers
69 views

Prove $\frac{-\log(1-x)}{x(1-x)}=1+(1+1/2)x+(1+1/2+1/3)x^3+…$

Let $0<x<1$. How can i prove the following identity: $$\frac{-\log(1-x)}{x(1-x)}=1+(1+1/2)x+(1+1/2+1/3)x^3+...\ \ .$$
5
votes
1answer
111 views

Asymptotic evaluation of integral of algebraic function

I am wondering what techniques exist for the asymptotic evaluation of integrals. Consider the integral $$ I(\lambda) = \int_1^\lambda dx \sqrt{1-\frac 1 x} = \sqrt \lambda \sqrt{\lambda - 1}- \cosh^{-...
1
vote
1answer
84 views

Probability of picking each of m elements at least once after n trials.

Suppose I have 10^9 distinct elements, and an equal probability of picking each one in a given trial. How many trials must be conducted for the probability of having picked every element at least once ...
0
votes
2answers
21 views

How can I prove that Cx will intersect x^2

I want to disprove $ cx \geq x^2 \ \forall \ x $ where c is a real number. (i.e. show that x^2 is not O(x) ) So it seems that I can show that the two must intersect at some point ... if I divide both ...
0
votes
0answers
24 views

Different Upper and Lower Bound

Is there a function or algorithms whose upper bound and lower bound are different? For example f(X) i.e f(X) = O(X^2) and f(X) = Omega(X)
0
votes
2answers
81 views

Asymptotics of $\sum \sqrt{k}$ and $\sum (-1)^k\sqrt{k}$

I was playing around with series recently and asymptotics of $\sum \sqrt{k}$ and $\sum (-1)^k\sqrt{k}$ were required to solve another problem. I have dealt with the first one using an integral ...
0
votes
1answer
41 views

Name of the difference between an asymptote and the curve that approaches it

Consider a function, say a hyperbola, and its asymptote. Is there a specific term for the difference between the two? Answers specific to hyperbola, as well as answers about general terminology, are ...
1
vote
1answer
125 views

Asymptotic Expansion of an Integral involving Modified Bessel Functions

I do not have enough experience with the asymptotic expansion of integrals especially involving Bessel functions. I appreciate any feedback that you guys provide. Here is the problem. Let $a$ and $b$ ...
1
vote
1answer
31 views

Running Time Question

In what situations would a function of $\theta(n^2)$ perform better than $\theta(n \log n)$? I noticed that in comparing the two, they intersect at $n = 4$. After this, $n \log n$ takes over as ...
3
votes
1answer
100 views

How to give an upper bound for a solution of $T(n) = T(0.25n) + T(0.75n) + O(n)$?

We have an algorithm which can be described the recurrence formula: $T(n) = T(\frac{n}{4}) + T(\frac{3n}{4}) + O(n)$ and for $n\le 100$: $T(n) = O(1)$. How to show that $T(n) = O(n \log n)$? ...
0
votes
2answers
24 views

Dominance and Big Oh problem

What is the dominant term in the following expression? 100n + 0.01*(n^2) It is confusing because the power function should be growing faster than the linear function regardless the constants. But ...
3
votes
1answer
44 views

Algebraic number with bounded coefficients

How many algebraic numbers $z$ are there satisfying $P(z)=0$ where $P(z)$ is some polynomial with integer coefficients of degree less than or equal to $n$ such that the absolute value of every ...
2
votes
1answer
47 views

Asymptotic solution to inequality $x < k \ln(1+x)$

What is an upper-bound on $x$, given that $x < k \ln(1+x)$? I believe that the solution is something of the form $\mathcal{O}(k \ln k)$ but I am unable to prove this. This is my first encounter ...
1
vote
2answers
1k views

Find the asymptotes of the Parametric equation?

Consider $$ x(t) = 2 e^{-t} + 3e^{2t}$$ $$y(t) = 5 e^{-t} + 2 e^{2t}$$ which represents a non rectilinear paths Horizontal and Verical Asymptotes : If $t \rightarrow +\infty \ \ or \ \ -\infty$, ...
0
votes
1answer
20 views

Confirm the answer to compute the asymptotic solution to the problem

I have the following problem The solution I derived is $O(g(n))$ where $C = 1, n > 1$. Is this solution correct ?
1
vote
1answer
78 views

Run time/Efficiency of finding Least Common Multiple

The algorithm is: $$\mathrm{lcm}(x,y)=\frac{xy}{\gcd(x,y)}$$ And we can use the Euclidean algorithm for finding $\gcd$. How is the complexity for above method $O(n^3)$, if $x,y$ can at maximum ...
2
votes
0answers
92 views

Asymptotic expansion of integral of $e^{-t}/t^n$.

So we study $$f_{n}(x) = \int_x^{+\infty} \! \frac{e^{-t}}{t^{n}} \, \mathrm{d}t, \quad n \in \mathbb{N^{*}}.$$ I've shown that for every $n$, $f_{n}(x) \sim_{+\infty} \frac{e^{-x}}{x^{n}}$. Now I'...
1
vote
1answer
99 views

Infinite sum of asymptotic expansions

I have a question about an infinite sum of asymptotic expansions: Assume that $f_k(x)\sim a_{0k}+\dfrac{a_{1k}}{x}+\dfrac{a_{2k}}{x^2}+\cdots$ with $a_{0k}\leq \dfrac{1}{k^2}$, $a_{1k}\leq \dfrac{1}{k^...
0
votes
1answer
39 views

How do limit cycles explain curvilinear asymptotes?

I'm a 17 years old and I have no clue about a concept known as limit cycles. I looked it up and I understand it represents the orbit of functions approaching other A person told me that limit cycles ...
0
votes
1answer
109 views

How to prove a recurrence with multiple terms?

I have to prove that the recursion: $$T(n) = T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + n $$ is $$ T(n) = Θ(n*\log n)$$ As you can see, the reccurence has two different terms that ...
0
votes
1answer
35 views

Approximating a binomial sum over a simplex

For partial binomial sums such as $\sum_{k\le\Delta} \binom{n}{k}$ we don't tend to have closed forms. However we still know asymptotic expansions that are easy to work with. Can we do something ...
1
vote
0answers
37 views

Complexity of $T(n) = T(n-10) + \sqrt{n}$

I'm using the iteration method to find the complexity of the following recurrence (I can't use the master theorem because it doesn't match the MT form). $$ T(n) = T(n-10) + \sqrt{n} \text{ and } T(1) ...
1
vote
1answer
61 views

Asymptotic and 3-SAT problem in Algorithm Course

my TA says just one of the following is True, anyone could describe me some detail about following three lines? 1- if $f_i$ be a function of natural numbers to natural numbers and $f_i(n)=O(n)$ then ...
0
votes
2answers
67 views

Big $O$ notation - $n ^ {\log n}$ versus $2^n$

I received an asymptotics question for my homework, which is to compare the orders of growth for $f(n)$ and $g(n)$ where: $f(n) = n^{\log(n)}$ $g(n) = 2^n$ I have an intuition that $f(n) = O(g(n))$,...
0
votes
1answer
28 views

Asymptotic form when series form of a real analytic function is known

Given an analytic function $f: \mathbb{R} \to \mathbb{R}$ whose Taylor series converges over all $\mathbb{R}$ and is \begin{equation} f(z) = \sum_{k=0}^{\infty}a_k x^k, \end{equation} and where the ...
2
votes
0answers
68 views

Picking codewords that are close

Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and number of minimum weight codewords $N_d$. How many ways can you select codewords $c_1,\dots,c_T$ (assume $T\ll q^k$) such ...
2
votes
1answer
79 views

Asymptotic bound of the series $\sum_{n\leq x}\log n / \varphi(n)$

Could someone give me a hint on the computation of the asymptotic bound for the following series $$ \sum_{n\leq x}\frac{\log n }{ \varphi(n)}\,, $$ where $\varphi(n)$ is the Euler totient function? ...
0
votes
0answers
27 views

Differential Equation for Algorithm Time

I'm working on algorithm analysis and time complexity. I've got a homework assignment to calculate a function f(n) at time t and I want to figure out how to write it as a differential equation. Haven'...
2
votes
1answer
102 views

How can we compute best-case and/or average-case and/or worst-case running-time knowing some of them?

Complete the table when it is possible. $$ \begin{array}{c|lcr} \mathrm{Algorithme} & \text{worst-case} & \text{average-case} & \text{best-case} \\ \hline A & O(n) & ... & \...
0
votes
1answer
32 views

How may times should I colour a colour palette to have distinct colours?

Suppose that we have a colour palette, i.e., an array of n elements, which needs to be coloured by distinct numbers. We are only allowed to use 0 or 1 to colour every elements in each colouring step. ...
3
votes
1answer
63 views

Second-order asymptotics for $\pi(n), \theta(n)$

Let $\pi, \vartheta$ be respectively the prime counting function and the first chebyshev function. As you know, $ \pi(x) \sim x/\log x$, and $\vartheta(x) \sim x$, so that, at first order, seems $\pi(...
0
votes
1answer
50 views

Question involving summations and the Θ-notation of running times

I think I understand the concept of summations and Θ-notations, however, I don't really understand the question below. If I have understood it correctly, I'm supposed to write out the summations (...
0
votes
1answer
82 views

Elementary proof that $\omega(n)$ is bounded $\frac{\log n}{\log( \log n)}$ in the limit?

I'm trying to show that $\omega(n)$ is less than $\frac{\log n}{\log(\log n)}$ as it's stated without proof in an analytic number theory text. It's a corollary of the PNT, but I want to not use that ...
0
votes
1answer
55 views

Time Complexity for Asymptotic Functions

Here below I have a problem set where I am asked to define the relationship between f(n) and g(n). I have added in my solutions but I wanted to get my answers checked by you guys before I turn this in....
1
vote
1answer
40 views

Confusion about Big O notation

I have a somewhat stupid question regarding the "Big O" notation: Is there any difference between saying $f=O(g)$ and $f\le O(g)$?
0
votes
0answers
41 views

recursive-algorithm problem

I am not to sure were to begin Thanks
0
votes
1answer
13 views

Linking summations with their correct function(s)

Guys can you please guide me step by step on how to link given functions with the functions to choose from. So for example a function $g(n)\in \Theta n^2$ and if there is no match then you say there ...
1
vote
1answer
39 views

Asymptotic Notation Analysis Problem

I'm new here. I have some question on asymptotic analysis I am trying to calculate the Big-O of these five functions and rank them up: a: $$2^{log(n)}$$ b: $$2^{2log(n)}$$ c: $$n^{5\over2}$$ d: $$2^{...
2
votes
0answers
42 views

Asymptotic behavior of $1/(a^2+\epsilon^2)$ as $\epsilon\to0$

A limit that often arises in physics is $$ \lim_{\epsilon \to 0} \frac{ \epsilon }{ a^2 + \epsilon^2 } = \pi \delta(a) ............ (1) $$ Is there a similar sort of limit for $$ \lim_{\epsilon \to 0} ...
2
votes
4answers
140 views

Limit and infinite sums. Finding $\lim_{x\rightarrow\infty}\sum^{\infty}_{k=1}\frac{1}{k^3 x-k^2}$

Could anyone help me with this problem. Compute $$\lim_{x\rightarrow\infty}\sum^{\infty}_{k=1}\dfrac{1}{k^3 x-k^2}$$ I don't know how to change a limit and a sum. Could you help me with this problem ...