All Questions
Tagged with logarithms algorithms
130
questions
2
votes
2
answers
104
views
I was trying to understand QUAKE III fast inverse square root alg and i want to find best 'u' value in $\log_2(x+1)≈x+u$ approximation
I was trying to find best 'u' value for this approximation:
$\log_2(x+1)≈x+u$
And I did think I can calculate error with this function.
NOTE: for the x values between 0 and 1 i need becouse of IEEE ...
- 53
0
votes
1
answer
56
views
What is this kind of recursion?
Consider the following expression:
For any fixed integer $a$, for real $x_i$
Pick an $x_0$ such that
$ln(ln(a))/ln(ln(a*100*x_0))=x_1$
Then substitute $x_0\mapsto x_1$
$ln(ln(a))/ln(ln(a*100*x_1))=x_2$...
- 591
0
votes
2
answers
51
views
Is $a\log_2(b) \le b\log_2(a)$ for all $a$ and $b$ given that $1 \le b \le a$?
I am trying to optimize the number of comparison in the merge sort algorithm, particularly during the merging step.
Is $a\log_2(b) \le b\log_2(a)$ for all $a$ and $b$ given that $1 \le b \le a$?
I ...
- 507
0
votes
2
answers
59
views
$g(n)$ upperbounds $f(n)$ but graph shows otherwise
Given we have the following functions:
$$f(n)=\log_{2}^{4}n$$
$$g(n)=2^{\sqrt{\log_{2}n}}$$
I've done the limit of f(n) over g(n), and found that g(n) is an upperbound of f(n) given the zero result:
$$...
1
vote
1
answer
78
views
Is there an intuitive reason natural logarithms arise in the analysis of randomized quicksort?
The randomized quicksort algorithm works as follows:
If the list to sort is empty or has length one, it’s sorted.
Otherwise, pick a uniformly random element of the list called the pivot element. ...
- 10.5k
0
votes
0
answers
175
views
How to maximize the geometric mean? - SLSQP would be correct?
I am trying to find a set of weights for each asset in the portfolio, that would give me the highest geometric mean, with only the constraint that all weights must sum up to 1. I'm currently using the ...
1
vote
1
answer
80
views
What is the right solution for this algorithm analysis?
I am having a problem from Algorithm Design Manual, this problem want me to provide a $f(n)$ of this code that I can directly use that to calculate the value of $result$. After several tries I come to ...
- 125
0
votes
2
answers
65
views
Generalized MergeSort time complexity functional equation: $f(n)=2f\left(\frac{n}{2}\right)+cn$
There is a well-known solution to MergeSort time complexity problem. It reduces to solving the following functional equation:
$$f(n)=2f\left(\frac{n}{2}\right)+cn$$
It isn't that difficult to solve it ...
- 1,488
2
votes
3
answers
253
views
Is $\log(n!)=o(\log(n^n))$?
This is a question from CLRS (3rd edition, Pg 61) :
I have to find out whether
$\log(n!) = o(\log(n^n))$
( Note it is Little-oh)
From this & this question, I can see why $\log(n!) = O(\log(n^n))$...
- 31
1
vote
2
answers
1k
views
Applying log on both sides to decide whether $f(n)=O(g(n))$ or $g(n) = O(f(n))$?
If i have to decide which function is bigger, can i apply logarithm on both sides and infer?
For example, $n $ vs $\sqrt n$
[On face of it i know that n>$\sqrt n$]
If i apply log function
$\ln n $ ...
2
votes
2
answers
122
views
Halving input but not at each step of a process
I am reading about an algorithm that takes as input $2$ integers and does the following to calculate the GCD:
If both are even then then shift right (=division by $2$) both numbers and repeat
If one ...
- 1,609
0
votes
1
answer
136
views
Recurrence Tree Method: $T(n) = 3(2n/3) + 1$ Why is the solution in $\log_{3/2}$ and not base $\log 2/3$?
I feel this is more of a question in the logarithms, but I am confused why this tree reoccurrence
$$T(n) = 3T(2n/3)+1$$
solution is derived from $\log_{3/2}$ rather than $\log_{2/3}$? My thinking ...
- 187
1
vote
1
answer
351
views
Experimental Analysis of an Algorithm - How to prove that the graph is $O(n\log n)$?
This question is probably stupid, but I've been trying to figure this out for hours and I still couldn't find anything about it. Probably I'm just too lost.
So basically, I'm analysing an algorithm by ...
- 13
-1
votes
1
answer
57
views
Asymptotic notation proof question
Note: We defined asymptotic notation for functions $f : \mathbb{N} \to \mathbb{N}$, but the same definitions work for real-valued functions $f : \mathbb{N}\to\mathbb{R}$.
Let $f, g : \mathbb{N}\to\...
0
votes
1
answer
81
views
iterative logarithm and one asymptotic example
we know about iterative logarithm like as Here.
there are some typo in my note, so I update the question into:
which of them is correct from asymptotic point of view? there is no need to proof, an ...
- 324