# Tagged Questions

38 views

27 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 ...
108 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 ...
212 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?
137 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 ...
43 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?
237 views

147 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 ...
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: ...
170 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 ...
141 views

### expanding functions with logs to find Big-O estimate

...
377 views

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 ...
109 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 ...
166 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$ ...
234 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 ...
102 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!
62 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 ...
167 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)))$ ...
282 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 ...
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 ...
74 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 ...
### 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!
### 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 ...