0
votes
0answers
41 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
22 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
28 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
47 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
42 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
49 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
29 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
85 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
181 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
76 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
428 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
33 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
34 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
32 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
56 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
49 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
57 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
162 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
456 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
440 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
117 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
266 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
138 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
45 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
258 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
88 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
134 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
156 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 ...
5
votes
2answers
2k views

Value of Summation of log(i)

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: ...
1
vote
1answer
190 views

little o notation with natural logs

I'm having trouble with little o notation. Help me show that: $2(n^2 + 100n)\log^5n = o(n^2\sqrt{n})$. It is the last hwk on my sheet and I don't understand it, if someone can help me with ...
1
vote
1answer
148 views
1
vote
1answer
379 views

Sum of series with log in each term

I was solving recurrence relation of Introduction to Algorithms by {Cormen, Leiserson, Rivest, Stein}, 3rd. edition. Problem 4-3 (i) $$ T(n) = T(n-2) + \frac{1}{lg \; n} $$ I tried few ways, like ...
1
vote
1answer
115 views

Big O with Log base equivalences and a question about sum of series.

Hi I need help figuring these out: True or False: $\log_2 n$ is $O(\log_3 n)$ I used the definition of Big O in Dasgupta's book: ${f(n)}\over g{(n)}$ $\leq c$ So I used the base transformation rule ...
-1
votes
1answer
174 views

How to find asymptotic entire functions?

I want to know how to find analytic functions $f(z)$ that are asymptotic and analytic on and near the real line of functions of the type $\ln(C +\exp(P(z^2)))$ where $C$ is a complex constant and $P$ ...
0
votes
3answers
251 views

Maple Error on Asymptotic Analysis of $\ln(n)!$

In Maple, the command asmypt($f$,$x$) computes the asymptotic expansion of the function $f$ with respect to the variable $x$ (as $x \rightarrow \infty$). The command asympt(ln(n)!,n); gives the ...
1
vote
1answer
103 views

Prove that $\log \log y = \mathcal{o}(\log y) + \mathcal{O}(1)$.

I just wanted some help to prove that $$\log_2 \log_2 y = \mathcal{o}(\log_2 y) + \mathcal{O}(1),$$ when $y = f(n) \in \mathcal{O}(n)$ and $y > 4$. Thanks!
0
votes
0answers
63 views

Question about an asymptotic analysis proof in Ball Collision Decoding paper.

On page 21 of Daniel Bernstein's paper "Smaller decoding exponents: ball-collision decoding" he presents a proof that I have a few questions about. $P,Q,R,L$ and $W$ are all positive and close to ...
0
votes
1answer
168 views

$\Theta$-notation of a logarithm

Given $H(x) = lg(f(n))$, where $f(n)$ is an asymptotically positive function, is it always true that if $f(n) = \Theta(g(n))$, then $H(x) = lg(\Theta(g(n)))$ $\Rightarrow H(x) = \Theta(lg(g(n)))$ ...
3
votes
1answer
301 views

predicting runtime of $\mathcal{O}(n \log(n))$ algorithm, one “input size to runtime” pair is given

I'm given the runtimes for input size $n=100$ of some polynomial-time (big-Oh) algorithms and an $\mathcal{O}(n \log(n))$ one. I want to calculate the runtimes for: $200$, $1000$ and $10000$. For the ...
2
votes
2answers
63 views

Can I simplify $\log_3{n} \cdot 2^{\log_3{n}} \cdot n$

Is it possible to simplify $$\log_3{n} \cdot 2^{\log_3{n}} \cdot n$$ I am actually trying to find the Big-O notation for this equation. But if you don't know what it is, is it possible to simplify ...
0
votes
2answers
76 views

Summation identity involving logarithm

I'm having trouble understanding why this identity holds: $$\sum_{k=0}^{(\log n) - 1} \frac{n}{\log (n - k)} + \theta(1) = \sum_{k=1}^{\log n} \frac{n}{k}+ \theta(1) $$ Any pointers to a proof ...
0
votes
2answers
165 views

how many bits to write $\sqrt x $?

x is an integer, and i can write it with $\log_2 x$ bit, and, viceversa, with $n$ bit i can write a number till $2^n$.. but.. how many bits to write $\sqrt x$ ? EDIT: the integer part!
5
votes
3answers
733 views

How to solve $n < 2^{n/8}$ for $n$?

This is from an exercise (1.2.2) in introduction to algorithms that I'm working on privately. To find at what point a $n \lg n$ function will run faster than a $n^2$ function I need to figure out for ...