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
41 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
18 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
64 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
230 views

Determine the number of paths of length 2 in a complete graph of n nodes

Question: Determine the number of paths of length 2 in a completed graph of n nodes. Give your answer in Big-O notation as a function of n So I started working on this problem however I know im doing ...
1
vote
1answer
80 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$ ...
2
votes
2answers
74 views

Upper bound for the sum $ \sum_{k=1}^N \frac{1}{\varphi(k)}$

Is there an upper bound for the sum $$ \sum_{k=1}^N \frac{1}{\varphi^{\alpha}(k)} $$ where $\varphi(n)$ is the Euler totient function and $\alpha\geq 1$ a real constant? In particular, I'm interested ...
1
vote
1answer
24 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 ...
1
vote
1answer
80 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 ...
0
votes
2answers
14 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 ...
2
votes
1answer
32 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
71 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
18 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 ?
0
votes
0answers
10 views

Upper bound for $T(n) = T(2n/3) + t(4n/9) + O(n)$

I got $T(n) = O(n^{11/9})$ as the answer. I just wanted to confirm if this is a correct bound and is there any tighter bound possible than this.
1
vote
1answer
38 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 ...
1
vote
4answers
99 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 ...
2
votes
0answers
48 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 ...
2
votes
0answers
60 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 ...
57
votes
1answer
1k views

Why are asymptotically one half of the integer compositions gap-free?

Question summary The number of gap-free compositions of $n$ can already for quite small $n$ be very well approximated by the total number of compositions of $n$ divided by $2$. This question seeks ...
2
votes
1answer
60 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
1answer
32 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 ...
2
votes
0answers
38 views

Effect of differentiation on function growth rate

For sufficiently "nice" functions, the differentiation operator appears to make slow growing functions grow slower and fast growing functions grow faster, with $e^x$ as a fixed point in the middle. ...
1
vote
2answers
448 views

Find the asymptotic growth of $t(n)$ satisfying $t(n)=2^nt(n/2)+n$

Find $\Theta$ of $t(n)$ for $$ t(n)=2^nt(n/2)+n .$$ I can't use Master Theorem because of $2^nt$ and althought I am familiar with other methods, I can't solve it. Is there a chance solve it ...
0
votes
1answer
18 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
22 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) ...
0
votes
2answers
53 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) = ...
0
votes
1answer
26 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 ...
0
votes
1answer
40 views

How would I find the big $\Theta$ of the following function?

$$f(n) = \frac{n}{\log(n)}$$ I understand the basics of how to find big O, Ω, and θ, however this particular function is giving me a lot of grief. To be more clear, I will give a simple example ...
0
votes
0answers
21 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. ...
1
vote
1answer
27 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 ...
0
votes
1answer
30 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. ...
0
votes
1answer
29 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
27 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 ...
1
vote
1answer
30 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
40 views
1
vote
1answer
20 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: ...
0
votes
1answer
41 views

Use recursion tree to give an asymptotically tight solution of T(n)

Assume $T(1) = 3.$ Recurrence is $T(n)=T(n-3)+3n+1$ and I'm showing $\Theta$ bound by computing the exact running time. Starting off: $(Tn-3) + 3n + 1$ $(Tn-9) + 9(n-3) + 3n + 1$ $(Tn-18) + ...
0
votes
1answer
49 views

Tight bound for $T(n) = T(n^{1/2}) + 1$ [duplicate]

Can someone help me figure out the big-O for the recurrence relation $T(n) = T(n^{1/2}) + 1$? I didn't think the master theorem would work since it requires $T(n) = T(n/b)$... to have $b$ as a ...
0
votes
1answer
42 views

How to give a big O estimate/visualize for these while loop?

This is from Discrete Mathematics and its applications I am currently working on problem 4. I was able to see that for problem 2, that one operation one will run n times for every n(meaning in ...
1
vote
1answer
43 views

Growth faster than polynomial, slower than exponential.

Assume $F(n)$ is a positive function. If $F$ is growing faster than a polynomial then is it growing exponentially fast? Is this statement true? Can we find a function $F(n)$ such that ...
0
votes
0answers
18 views

Limit of shifted ratios

Let $f$ a be a strictly positive function defined in the positive reals. Additionally suppose that for any $\delta > 0$ we have, as $t \to \infty$, $$ e^{-t^{1+\delta}} \ll f(t) \ll ...
0
votes
1answer
24 views

Show the correctness: $\log^3( n)\in o(n^{0.5})$

show the correctness: $\log^3 (n)\in o(n^{0.5})$? I started from this way $$\log \log \log( n) = n^{0.5}$$ then I take $\log$ for two parties $$\log\log\log\log( n) = 0.5 \log( n)$$ ...
3
votes
0answers
34 views

Algorithms - Solving the recurrence $T(n) = \sqrt{n} T \left(\sqrt n \right) + n$ [duplicate]

I have been trying to solve the recurrence $T(n) = \sqrt{n} T \left(\sqrt n \right) + n$ for some time now. I only know substitution, recursion trees, and the master method (though it doesn't apply ...
1
vote
1answer
56 views

Proving that one function is big o of another?

I'm working through a big-O problem and have the intuition to know the answer, but don't feel comfortable in my proof. I need to prove from definitions (i.e. proving that there exists two constants ...
0
votes
0answers
15 views

Bound from distinct integer summation

We want to find $r$ positive integers $\{a_i\}_{i=1}^r$ such that of atmost $(s+1)^r$ values obtained from $$\sum_{i=1}s_ia_i$$ where $s_i\in\{0,\dots,s-1,s\}$, we insist on some combination of ...
3
votes
2answers
84 views

Higher Order Terms in Stirling's Approximation

Some websites and books give stirling approximation as $$n! = \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n \left( 1 + O \left(\frac{1}{n} \right)\right)$$ However when I check their derivations most ...
0
votes
1answer
33 views

Solving recurrence relations using master's theorem

Can we solve following recurrence relation using Master's theorem- $T(n)=T(n/2)+\log n$ The thing to notice here is that, do $n (n^{\log b} a)$ and $\log n (f(n))$ have an exponential ...
0
votes
0answers
82 views

Implicit function where the Jacobian determinant is zero

When we have an implicit function defined by $f(x,y)=0$ where Jacobian determinant of $\frac{\partial f}{\partial x}$ is zero Let $x \in \mathbb{R}^n$, $p \in \mathbb{R}$ and $\phi:\mathbb{R}^n \to ...
1
vote
1answer
39 views

How to solve this triple summation problem?

For a computer science class we were asked to analyze the run time of an algorithm. The answer was posted. I am not sure the proof is correct. I believe the answer should be kc(n^2) (where k is a ...
5
votes
3answers
209 views

Use the Euler-Maclaurin summation formula to estimate a summation

$\sum_{k=0}^n \frac{1}{1+\frac{k}{n}}$ How can we estimate it to order $O(n^{-5})$ ?