0
votes
1answer
22 views

Comparing the order of convergence $\mathcal{O}( h^2 |\log(h)|)$

I don't have any intuition in judging how fast a term of the order $\mathcal{O}( h^2 |\log(h)|)$ is decreasing as $h \to 0$, so i tried comparing it with terms of the form $\mathcal{O}( h^\alpha )$ ...
7
votes
2answers
95 views

Why is this function a really good asymptotic for $\exp(x)\sqrt{x}$

$$f(x)=\sum_{n=0}^{\infty} a_n x^n\;\;\;\;\; a_n = \frac{1}{\Gamma(n+0.5)}$$ Why is this entire function a really good asymptotic for $\exp(x)\sqrt{x}$, where for large positive numbers, ...
2
votes
0answers
11 views

Comparing asymptotic growth of logarithmic functions by reasoning

As an exercise, we're sorting functions according to their asymptotical growth. When comparing these two functions, I'm getting stuck: $n^2/(\log_2 n)^3$ versus $n \log_2 n$. Using limits I am ...
0
votes
0answers
38 views

How is $O(\log(\log(n)))$ also $O( \log n)$?

How is $O(\log(\log(n)))$ also $O( \log n)$? I have seen this result somewhere with this but I still didn't quite understand how this is true. This would also help me compute Big Omega of the ...
3
votes
3answers
239 views

Find a real entire function $f(z)$ asymptotic to $\ln(x^2+1)$ for real $x$.

Find a real entire function $f(z)$ asymptotic to $\ln(x^2 +1)$ for real $x$. More specific I want $f(0)=0$ and $\frac{1}{2} \ln(x^2+1) < f(x) < 2 \ln(x^2+1)$. Or prove it does not exist.
0
votes
1answer
19 views

How do you solve a recurrence with a functin through induction?

I found the answer in part-A by substitution, as O(n) from; T(n/2^k) = T(1).... n/2^k = 1..... so k = 1og2(n)..... T(log2(n)) = T(n/n)+5.... so O(n) IS THE ANSWER, Correct me if am wrong because am ...
1
vote
1answer
34 views

Asymptotics of logarithm: $\frac{1}{n}\ln(a+o(1)) = \frac{1}{n}\ln(a)+o(\frac{1}{n})$

I am having problems with the use of the little oh notation my professor is adopting in the solutions to some exercises. As an example I do not understand why $$ \frac{1}{n}\ln(a+o(1)) = ...
1
vote
1answer
44 views

Find real-valued sequences $x(n)$ for which $c^{x(n)} = o(1/n )$

For which $x=x(n)$ does it hold that $$c^x = o\left(\frac{1}{n}\right)$$ where $c\in(0,1)$ is a constant. So clearly, for $x=n$, this is true. But for which $x =o(n)$ does this hold? I thought ...
0
votes
0answers
16 views

Normalizing Data for Graph

Firstly, sorry for the long post, but I must be detailed in my explanation here. This is a computer science heavy topic, and I've posted it on the CS section of Stack Overflow already, but the main ...
1
vote
2answers
46 views

Check my proof: Big O notation

I was asked the following: We are given the functions $f(n)=n^{10\log(n)}$ and $g(n)=(\log (n))^n$. Which of the following statements is true: $f(n)\in\mathcal{O}(g(n))$, $f(n) \in ...
0
votes
1answer
43 views

Why, or why not, is $5^{log_3(n)} \in \mathcal{O}(n^2)$?

Why, or why not, is $5^{\log_3(n)} \in \mathcal{O}(n^2)$ ? I tried transforming the logarithm to a base of 5, so that the logarithm and power cancel each other out. However, when I try to so I get ...
7
votes
1answer
231 views

An equivalent for $\int_0^1\left(\frac{1}{\log x}+\frac{1}{1-x}\right)^n\;dx$

Set $$ I_n :=\int_0^1\left(\frac{1}{\log x} + \frac{1}{1-x}\right)^n \:\mathrm{d}x \qquad n=1,2,3,.... $$ We have $$I_1 =\gamma, \quad I_2 =\log (2 \pi) - \frac 32, \quad I_3 = 6 \log A - ...
5
votes
2answers
104 views

How is $ \sum_{n=1}^{\infty}\left(\psi(\alpha n)-\log(\alpha n)+\frac{1}{2\alpha n}\right)$ when $\alpha$ is great?

Let $\psi := \Gamma'/\Gamma$ denote the digamma function. Could you find, as $\alpha$ tends to $+\infty$, an equivalent term for the following series? $$ \sum_{n=1}^{\infty} \left( \psi (\alpha ...
0
votes
0answers
52 views

Little o notation inequalities involving $n^{\log n}$

Apologies as this is a minor re-post, but I didn't think the other would get answers as it diverged into a discussion and got pushed down... I'm struggling with asymptotic notation a little bit... ...
1
vote
1answer
27 views

Using Stirling's approximiation to show that $(\log(\log n))!$ is $O(n^k)$

I am trying to show the following: Prove, using Stirling's approximiation, that $(\log(\log n))!$ is $O(n^k)$ for some positive constant $k$. Stirling's approximation is $$n!=\sqrt{2\pi ...
0
votes
1answer
32 views

Determine the realtions ($\mathcal{O}$,$\Theta$,$\Omega$ ) between $f(n) = \ln(n^{c} + n^{d})$ and $g(n)=\ln(n^{a} + n^{b})$

I am trying to determine the realtions ($\mathcal{O} $,$\Theta$,$\Omega$ ) between : $$f(n) = \ln(n^{c} + n^{d})$$ $$g(n)=\ln(n^{a} + n^{b})$$ Note: $a,b,c,d>0$ I need some advice how to use the ...
0
votes
1answer
31 views

Asymptotic behaviour of a couple of special functions (features exponentials and logarithms)

I'm dealing with a couple of functions: $n \log n$, $( \log \log n)^{ \log n}$, $( \log n)^{ \log \log n}$, $n e^{\sqrt{n}}$, $( \log n)^{ \log n}$, $n 2^{ \log \log n}$, $n^{1+1/( \log \log ...
-2
votes
1answer
48 views

Prove that $\log n = O(\log^2 n)$

Trying to solve this, but I can't seem to figure it out. Its fairly straight forward.
2
votes
4answers
44 views

Why is $\log(n) \in o(\frac{n}{\log(n)})$?

This would be equal to: $\forall c>0: \exists n_0 \in \mathbb{N}: \forall n>n_0: c\log(n) ≤ \frac{n}{\log(n)}$ For $c=1$ this is obvious, because $\log(n) ≤ \sqrt{n} = \frac{n}{\sqrt{n}} ≤ ...
1
vote
0answers
50 views

Is $\log^* (n+1)^{n+2} \in O(\log^* n)$?

I would like to know if $\log^* (n+1)^{n+2} \in O(\log^* n)$, where $\log^*$ is the iterated logarithm. I tried doing: $ \log^* (n+1)^{n+2} =\\ \log^{*}(\log(n+1)^{n+2})-1 =\\ \log^{*}((n+2) \cdot ...
2
votes
1answer
34 views

How to evaluate square of logarithms to solve s(n) = O(a(n))?

I've never used log before, nor worked with big-O notation, so I'm completely useless at this stuff. Any, any, any help or direction you can give would be helpful as the professor hasn't covered this ...
2
votes
2answers
93 views

Find the order of magnitude of the equation solution

Find the order of magnitude of the following equation solution: $$ x(\ln x)^{2001}=n $$
0
votes
1answer
213 views

Proving functions to be Big Oh

How do I determine if there exists a function $f$, such that \begin{equation} f(n) = {\mathcal O}(\log n), \end{equation} but \begin{equation} 2^{f(n)} ≠ {\mathcal O}(n). \end{equation} Is ...
0
votes
1answer
21 views

Using log of function to determine orders of growth

If I have functions $f(n)$ and $g(n)$ and I would like to determine $f(n) \in \Omega g(n)$ and/or $f(n) \in \Theta(g(n)$. Does proving $\log(f(n)) \in \Omega \log(g(n))$ imply $f(n) \in \Omega g(n)$? ...
3
votes
2answers
77 views

Why is $3^n$ not in $\Theta(2^n)$

How is it that $3^n$ not in $\Theta(2^n)$, while $log_3 n$ is in $\Theta(log_2 n)$ ?
0
votes
2answers
62 views

Asymptotics of two expressions involving logarithms

(As I am new to algorithmic complexity so), EDIT: please give solutions for large x (means as x->infinity) !
1
vote
0answers
24 views

Can an entire $f$ satisfy $x>k | f(x+yi)=\ln(x+yi+z)+o(1) $?

Let $z$ be a complex number. Let $i$ be the imaginary unit. Let $x,y,k$ be positive real numbers. Consider $$x>k | f(x+yi)=\ln(x+yi+z)+o(1) $$ true for all $x>k,y$ and some $k,z$. Is there ...
0
votes
2answers
572 views

merge sort vs insertion sort time complexity

How do I solve exercise 1.2-2 from Introduction to Algorithms 3rd Edition, Author: Thomas H. Cormen Would I need to set both sides equal to each other and solve for n?
2
votes
1answer
52 views

Show that $\operatorname{ln}(n!)=\Theta(n\operatorname{ln}(n))$

Another question about asymptotic approximations. We are asked to show that $\operatorname{ln}(n!)=\Theta(n\operatorname{ln}(n))$ I'm stuck tho and can use help. What I did is: ...
0
votes
0answers
34 views

check my short simple proof - Functions are of same magnitude. Asymptotic notation.

A simple question with a short solution I thought of, but I would like verification. $f(n)$ is a function that approaches infinity as $n$ approaches infinity. We are asked to show that ...
0
votes
1answer
35 views

Check my short proof - asymptotic approximation, which function is bigger

The goal of this exercise is to show that $\ln(n+1)-\ln(n) = O(\frac{1}{n})$ what I did is: I used the fact that if $f=O(g)$ then $\frac{f}{g}=O(1)$. $\ln(n+1)-\ln(n)=\ln(\frac{n+1}{n}) = \ln(O(1))$ ...
1
vote
2answers
35 views

Growth rate of $1/(\log(x)-\log(x-1))$

Let $x>1$ be a real number. Let $y=\dfrac{1}{\log(x)-\log(x-1)}$. My question: Approximately how fast does $y$ grow (asymptotically) in terms of $x$? (e.g. linear, polynomial, exponential)?
1
vote
1answer
33 views

Is $O(n \log n)$ always smaller than $O (m)$ for $n-1 < m < n^2$?

I am writing an algorithm that needs to finish in $O(m)$. The problem is for a graph $G( V, E )$, where $m = |E|$ and $n = |V|$. $m$ can be in the range of $n-1$ to $n^2 - 1$. If I do some ...
1
vote
2answers
68 views

Asymptotics of logarithms of functions

If I know that $\lim\limits_{x\to \infty} \dfrac{f(x)}{g(x)}=1$, does it follow that $\lim\limits_{x\to\infty} \dfrac{\log f(x)}{\log g(x)}=1$ as well? I see that this definitely doesn't hold for ...
1
vote
2answers
50 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 ...
1
vote
1answer
66 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) ...
-1
votes
1answer
197 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 ...
25
votes
1answer
464 views

Power towers: to infinity and all the way back

In the following, let $n$ be a positive integer, all other variables be real (furthermore, $a>1$), all functions be real-valued, and logarithms of negative arguments be undefined. Let ...
2
votes
1answer
51 views

Growth rate of Taylor convergents near pole

For any fixed $z_0\in\mathbb{C}\setminus \{0\}$ and $\beta\in\mathbb{R}^{+}$, prove that $$\left.T_n\left(\log^{\beta}z;z_0\right)\right|_{z=0}\sim\log^{\beta} n$$ Note: I observed that this holds ...
1
vote
2answers
562 views

Finding Big-O with Fractions

I'd want to know how I can find the lowest integer n such that f(x) is big-O($x^n$) for a) $f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1}$ I've fooled around with this a bit and tried going from $\frac ...
0
votes
1answer
28 views

Reduce Lethargy Equation

I need to prove that $$1-\frac{(A-1)^2}{2A}\ln \frac{A+1}{A-1}$$ approximately equals $\dfrac{2}{A+2/3}$. I think that we can expand the $\ln$ to $2(1/A+1/(3A^3)+\dots)$ and so the first term ...
1
vote
1answer
131 views

Asymptotic analysis - if f(n) = Ω(g(n)), how to prove ln(f(n)) = Ω(ln(g(n)))?

Is the following statement true, if so, how can I prove it? if f(n) = Ω(g(n)), is also true that ln(f(n)) = Ω(ln(g(n)))? Since ...
7
votes
1answer
297 views

How to compute the asymptotic growth of $\binom{n}{\log n}$?

I'm interested with tight bounds for: $$f(n)={n\choose{\log{n}}}$$ It sounds like it's something simple, but I can't get a nice expression I can use. Any ideas on how to do this?
1
vote
0answers
139 views

Using the gamma function as an upper and lower bound to the logarithm of a factorial function.

I am trying to find an upper and lower bound for the following function: $$f(x) = \ln(\lfloor\frac{x}{b_1}\rfloor!) - \ln(\lfloor\frac{x}{b_2}\rfloor!) - \ln(\lfloor\frac{x}{b_3}\rfloor!)$$ where ...
3
votes
1answer
46 views

What's the relationship between $O(\log(x+y))$ and $O(\log(xy))$

Which of these bounds, $O(\log(x+y))$ and $O(\log(xy))$, is tighter? Or are they equal?
1
vote
1answer
283 views

Big o notation $( n \log n + n \log(n^{\log n}))$

I'm trying to transform this: $$n \log n + n \log(n^{\log n})$$ into big O notation. I can't get to reduce the right part of the addition... Neither of these work: $$n^{\log n} ...
1
vote
1answer
89 views

$x \sim y \implies \pi(x) \sim \pi(y) $ and repeated applications of PNT

Let $\sim$ mean if $a \sim b$ then $\lim_{x \to \infty} \frac{a}{b} =1.$ The following is a threshold question. It seems that $x \sim y \implies \pi(x) \sim \pi(y).$ Pf. $\pi(x) \sim \frac{x}{\log ...
2
votes
3answers
137 views

$x \sim y \implies \log x \sim \log y$?

Does $x \sim y \implies \ln x \sim \ln y$? I would have thought not, but the following has almost persuaded me otherwise: Assume $x \sim y.$ Does this imply that $$\tag{1}I = ...
3
votes
1answer
162 views

What are the asymptotics of the solution to $\log x=\epsilon x$?

I just read the question Why does $\ln(x) = \epsilon x$ have 2 solutions?, and thought I'd point out a related area of investigation. The equation $\log x=\epsilon x$ has 2 solutions for ...
7
votes
2answers
2k views

Value of Summation of $\log(n)$

Context: I am learning Dijstra's Algorithm to find shortest path to any node, given the start node. Here, we can use Fibonnacci Heap as Priority Queue. Following is few lines of algorithm: ...