0
votes
3answers
28 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
18 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
65 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
59 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
1answer
219 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
27 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
18 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
295 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
53 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
77 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
22 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
367 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
245 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
72 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
102 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
49 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
31 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
77 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
377 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
184 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
131 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
289 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
190 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
391 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
159 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
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 ...
4
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 ...
23
votes
3answers
6k 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
397 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
631 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 ...