Tagged Questions
3
votes
1answer
31 views
Computing the period of a fraction polynomial in the number of digits
So I have a fraction a/b that is known to be repeating. How do I compute the period of the repeating decimal in polynomial-time in the number of digits of A and B?
2
votes
1answer
98 views
How to show that Eratosthenes sieve algorithm has a complexity of $O(n\log n)$
I know this is a loose upper bound, but I am in an entry level CS course that is just trying to get us used to evaluating algorithms. Any pointers on how to move forward on this problem?
0
votes
0answers
54 views
Calculate time complexity of modular arithmetic
I wanted to calculate $a \mod n$. What is the time complexity of this? I'm using a Java program?
Can anyone provide an explanation of the time complexity for the following calculations?
$$c=a \cdot ...
1
vote
1answer
35 views
Why does it take maximum of $n/\log n$ digits to represent the number $2^n - 1$ in base of $n$?
Given the number $n$. Why does it take maximum of $\frac{n}{\log n}$ digits to represent the number $2^n - 1$ in base of $n$?
4
votes
1answer
58 views
Number of solutions $x_1x_2\dots x_k = n, x_i, n \in \mathbb{N}$
Here's a question I've been asked:
Let $n\in \mathbb{N}$ and let $d_k(n)$ be the number of solutions of
$$x_1\dots x_k = n, \hspace{5mm}x_i\in \mathbb{N}$$
I need to show
$$d_k(n) = ...
5
votes
0answers
367 views
The Average Running Time Of Euclid Algorithm?
What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$?
It seems very hard to deduce from the recurrence
$T(m,n) = T(n, m ...
9
votes
2answers
231 views
An interesting way of producing positive integers
If we define $$\cal N _1 := \{ 1\} $$ and by induction $$\cal N_{n+1}:=\{x\in \mathbb N | \exists a,b \in\cal N_n : x= a+b \text{ or }x=ab \text{ or }x=a^b \}$$
it's easy to prove that, for every $m ...
1
vote
2answers
403 views
Factoring n, where n=pq and p and q are consecutive primes
So in RSA, there is a modulus n which is the product of two primes.
My question is regarding when p and q are consecutive primes, what would the time complexity be? So, n=pq and p and q are ...
