1
vote
2answers
23 views

What algorithm solves this problem? Non-linear measuring tape

A measuring tape is marked at 0, 5, 15 and 40. The distances between each mark are marked on top. At what distances should I mark 1 through 4, as well as 6-14 and 16-39? My math knowledge does not ...
0
votes
1answer
18 views

Logarithm Base Question

Suppose you have a integer n. Log2(n) is supposed to be ~ the number of times you have to divide n by 2 until you reach one. Now let's say you want to know ~ the number of times you have multiply n by ...
0
votes
0answers
40 views

How is $O(\log(\log(n)))$ also $O( \log n)$?

How is $O(\log(\log(n)))$ also $O( \log n)$? I have seen this result somewhere with this but I still didn't quite understand how this is true. This would also help me compute Big Omega of the ...
3
votes
1answer
87 views

Base of logarithm decrease when variable count increase

I run a large online platform where users submit articles and earn points. I am working on an algorithm where the more comments they submit, the higher score they will receive. In its simplest ...
3
votes
3answers
65 views

How to generate $\log$ function that intersects at $(0,1)$ and $(1,0)$?

I apologize for any incorrect or missing formatting, first time posting in the math stack exchange. It's been a few years since I've done any kind of calculus, so I remember nothing at all, which is ...
0
votes
0answers
28 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
82 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
48 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
49 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
28 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
92 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 ...
2
votes
2answers
78 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
589 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
35 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
20 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
402 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
70 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
70 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
578 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
265 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
126 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
84 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
38 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
80 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
385 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
190 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
412 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
199 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
500 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
321 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
405 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
688 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 ...