0
votes
0answers
24 views

Using math functions to time finales of a fireworks show

This year, I have the honor of programming two finales for a fireworks show. I want to use math. I suspect that I should use a function such as square root or log to specify the decreasing pause ...
2
votes
1answer
76 views

Logarithm of $\frac{a^k}{a^k-1}$

On a question on this site there is an explanation of the algorithm Knuth gives in The Art Of Computer Programming to compute an approximation of $y = \log_bx$. Now, I understand why it works; ...
-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.
0
votes
3answers
43 views

How do you solve a equation by converting to logarithm form for the problem$3e^{x-4} +2=83$?

$3e^{x-4} +2=83$ I understand converting logarithms but i dont understand how to convert e into log form and solve. help would be deeply appreciated.
0
votes
1answer
23 views

What is the sum of recursive logarithms?

I am trying to deduce the complexity of a rather odd algorithm. I have got it down to this form: $$ O(n \times (\sqrt n)^2 + n \times (\lg \sqrt n)^2 + n \times (\lg \lg \sqrt n)^2 + \space ... + ...
1
vote
1answer
88 views

How do computers calculate the log of a value? [duplicate]

I'm not sure if this question belongs on StackOverflow or here (please let me know if the former, and i'll delete this and ask there), but I was wondering how the ...
1
vote
2answers
69 views

Can I add $\log$ to both sides of inequality such way?

Can I add $\log$ to both sides of the following inequality $$f(n) \leq cn^k$$ and get $$\log (f(n)) \leq kc\log n$$ I know that by rules the result inequality should be like this $$\log(f(n)) \leq ...
0
votes
2answers
441 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?
0
votes
1answer
33 views

Calculating an exponentially increasing vector of points in a test and measure system

My application is setting and measuring current and voltage in a physical system with a software algorithm. Given these parameters: min, ...
0
votes
1answer
19 views

Diffie hellman and the discrete algorithm problem

Suppose Alice and Bob are exchanging keys using Diffie-Hellman Key-Exchange Algorithm. a - Alice secret key g - generator p - prime x - the public key passed from Alice to Bob. Eve is listening to ...
5
votes
1answer
378 views

Why does the method to find out log and cube roots work?

To find cube roots of any number with a simple calculator, the following method was given to us by our teacher, which is accurate to atleast one-tenths. 1)Take the number $X$, whose cube root needs ...
0
votes
1answer
63 views

How do I go about manipulating this summation equation to solve it?

In my textbook, Introduction to Algorithms, the following is shown: And I believe I understand that. However, I have a similar equation to the one on the first line, but instead of ...
0
votes
2answers
69 views

How does my professor go from this logarithm to the next?

In the above picture, how does he go from the third-last line to the second last?
2
votes
2answers
79 views

Inequality $C\lceil\log{n}\rceil! \geq n^k$

I've been struggling to prove there exist $C$ for $n, n_{0}, \forall k >0 \in \mathbb{R}$ such that $\forall n > n_{0}$: \begin{equation}C\lceil\log{n}\rceil! \geq n^k\end{equation} As you ...
0
votes
1answer
27 views

Rounding to the nearest term in a geometric progression

Consider the following progression: where i is ith number within the progression. I would like to devise an equation that will round input value to the nearest number from this progression. For ...
1
vote
2answers
447 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 ...
6
votes
6answers
254 views

Elegant way to solve $n\log_2(n) \le 10^6$

I'm studying Tomas Cormen Algorithms book and solve tasks listed after each chapter. I'm curious about task 1-1. that is right after Chapter #1. The question is: what is the best way to solve: ...
1
vote
1answer
42 views

Complexity analysis of logarithms

I have two functions, f(n)=log(base 2)n and g(n)=log(base 10)n. I am trying to decide whether f(n) is O(g(n)), or Ω(g(n)) or Θ(g(n)). I thinks i should take the limit f(n)/g(n) as n goes to infinity, ...
3
votes
1answer
75 views

Solving the recurrence: $h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1 $

I want to solve the following recurrence: \begin{equation} h(1) = 0\\ h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1 \end{equation} What are some basic "methods" I can use to guess a ...
1
vote
0answers
113 views

Is this “Elegant” algorithm for logarithm by Zeckendorf representation, the same as an 'efficient' algorithm?

The algorithm here which computes the exponent $b$ given a base $a$, and given $n$ = $a$^$b$, appears no better to me than simply counting the number of times we divide $n$ through by the base $a$ ...
0
votes
4answers
59 views

How to understand that sequence is logarithmic?

Let's say I have example of phonebook lookup. I need to find one record in it. I can always divide phonebook into 2 equal parts and try to find a record in that way. ...
0
votes
1answer
34 views

Bounding below the difference of sums

I would like to bound below the following expression: $\lambda(m,n)=\sum\limits_{i = 1}^{m+n}\lg{i} - \sum\limits_{i = 1}^{m}\lg{i} - \sum\limits_{i = 1}^{n}\lg{i}$ by some expression that ideally ...
0
votes
2answers
79 views

Explanation needed on this rather basic recurrence solution

We are studying about recurrences in our analysis of algorithms class. As an example of the substitution method (with induction) we are given the following: $$T(n) = \lbrace 2T\left(\frac{n}{2}\right) ...
1
vote
1answer
77 views

What kind of series / recursion is this?

I'm trying to find the explicit solution / sum of first n elements for the following sequence: d(2) = 2 d(n) = d(n/2) + n*log2(n) Can you help me to find out ...
1
vote
1answer
380 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
187 views

Numbering primes within a range.

$$n\ln n + n\ln\ln n−n < p_n < n\ln n+n\ln\ln n \mbox{ for } n\geq 6$$ This is the range where the $n$-th prime must lie. However sieving within this range generates a large number of primes. ...
1
vote
4answers
134 views

$\log_2$ approximation in $[1,2)$

this is realistically for a programming project, but is more math centric then CS centric. I am attempting to write a function that approximates a power function, but in order to complete I need to ...
1
vote
1answer
320 views

simple calculation using logs

Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size $n\in\mathbb{N}$, insertion sort runs in $8n^2$ steps, while merge sort runs in ...
0
votes
2answers
198 views

How do you solve this simple logarithm problem?

I'm comparing efficiencies for the famous fake-coin algorithms. Specifically, I'm looking at a two-pile approach and a three-pile approach for a solution. I have found that, like a binary search, ...
2
votes
3answers
429 views

How can I solve $8n^2 = 64n\,\log_2(n)$

I currently try to analyze the runtime behaviour of several algorithms. However, I want to know for which integral values $n$ the first algorithm is better ($f(n)$ is smaller) and for which the second ...
2
votes
1answer
160 views

Are all logarithms multiple of each other?

I was doing a time complexity problem, and the solution mentioned that there is a single class for logs. Ie. we can write $\log_a (x) = \Theta(\log_b(x))$ where $a$ is not equal to $b$. This can be ...
3
votes
1answer
303 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 ...
5
votes
1answer
1k views

How does Knuth's algorithm for calculating logarithm work?

I had a look at Knuth's The Art of Computer Programming, book 1. In chapter 1, section 1.2.2, exercise 25, he presents the following algorithm for calculating logarithm: given $x\in[1,2)$, do the ...
25
votes
3answers
7k views

What algorithm is used by computers to calculate logarithms?

I would like to know how are logarithms calculated by computers. The GNU C library, for example, uses a call to the fyl2x() assembler instruction, which means that ...
9
votes
1answer
401 views

Is there a binary spigot algorithm for log(23) or log(89)?

The Bailey-Borwein-Plouffe formula yields a binary spigot algorithm for π, and related formulas give the bits of log(2) and those of the logarithms of some other integers. I got stuck (over a year ...
0
votes
1answer
666 views

Logarithm base 2 and factorials

I'm learning about $\log_2$ for an algorithms class and theres a problem in the book that is confusing me. It asks: Find a formula for $\log_2(n!)$ using Stirling's approximation for $n!$, for large ...