Tagged Questions
1
vote
1answer
37 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 ...
5
votes
1answer
67 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
101 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
31 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
103 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
75 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
94 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 = ...
2
votes
1answer
79 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 ...
3
votes
2answers
172 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
109 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
82 views
1
vote
1answer
281 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
71 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
138 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
178 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
94 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
56 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
121 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
167 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
61 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
73 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
153 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!
4
votes
3answers
531 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 ...
