0
votes
2answers
80 views

Any power of logarithm is $O(N)$

This is more of a computer science question but it uses calculus and proof techniques so I think it might be more appropriate here. Basically, how do I prove that, for any constant $K \geq 1$, ...
1
vote
1answer
24 views

Taking the log of both sides to determine big Theta/Omega/O

I've managed to confuse myself over this detail: Obviously: $n^2 \notin \Theta(n)$ Now if we take the $\log$ of both sides, we get: $$\log(n^2) \leq \log(cn)$$ $$2\log(n) \leq \log(c) + \log(n)$$ ...
1
vote
2answers
22 views

Prove that the binary representation of a number n will use floor(lg(n)) + 1 bits.

I'm taking Computer Algorithms class and one of my problems is from Skiena's Algorithm Design Manual, 2-41: Prove that the binary representation of $n \ge 1$ has $\lfloor \lg n \rfloor +1$ bits ...
0
votes
1answer
42 views

Polytime implementation of Discrete Log using primitive recursive functions

The primitive recursive functions are defined by Godel as: $z() = 0$ $s(x) = x+1$ $\pi_i(x_1, \dots, x_k) = x_i$ Plus closure under Composition: $h(x_1, \dots, x_m) = f(g_1(x_1, \dots, x_m), ...
1
vote
1answer
73 views

Making a logarithmic equation that starts at $(0,0)$ and passes through $(x, y)$?

I'm writing a computer program and for fading sound, it's best to do it in a logarithmic equation. What I need it to find a graph of the "volume" that starts at (0, 0) [x is the time, y is the volume] ...
5
votes
1answer
260 views

Explain this code to compute $\log(1+x)$

It's well known that you need to take care when writing a function to compute $\log(1+x)$ when $x$ is small. Because of floating point roundoff, $1+x$ may have less precision than $x$, which can ...
0
votes
1answer
132 views

first 1 in a bitmask using log2

I am trying to get the last 1 in a bitmask. More mathematically speaking, I have a number k, that can be written in its binary form as a sequence of 1 and 0. I want the "weight" or "index" of the last ...
1
vote
3answers
83 views

Simplifying logs?

Would $\log_2 (n+1)$ simplify to $\mathcal{O}(\log_2 n)$? I wasn't sure if this was valid since logs aren't distributive and I couldn't find a constant $c$ relating the expressions. If this turns ...
4
votes
1answer
90 views

A logarithmic equation?

$$\mathcal{O} \left(3^{\log_2(n)} \right) = \mathcal{O} \left(n^{\log_2(3)} \right)$$ Does anyone have any idea how the right side was arrived at? (The $\mathcal{O}$ is Big-$\mathcal{O}$ notation)
3
votes
1answer
337 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
4answers
242 views

Mathematical notation/name for the number of times a number can be divided by 2

I am using this simple snippet of code, variants of which I have seen in many places: for(int k = 0 ; n % 2 == 0 ; k++) n = n / 2; This code repeatedly ...