Articles of computational complexity

Binary search complexity

In sorted array of numbers binary search gives us comlexity of O(logN). How will the complexity change if we split array into 3 parts instead of 2 during search?

What is the running time of this algorithm of prime factorization?

I recently figured out my own algorithm to factorize a number given we know it has $2$ distinct prime factors. Let: $$ ab = c$$ Where, $a<b$ Then it isn’t difficult to show that: $$ \frac{c!}{c^a}= \text{integer}$$ In fact, $$ \frac{c!}{c^{a+1}} \neq \text{integer}$$ So the idea is to first asymptotically calculate $c!$ and then keep […]

Given a graph, can we delete exactly k edges and the minimum degree of remaining graph is at least 4

Given a graph, can we delete exactly $k$ edges to make the minimum degree of remaining graph at least $4$? Or given a graph what is the maximum number of edges can we delete to make every vertex in remaining graph has at least 4 degrees?

set of Kolmogorov-random strings is co-re

given RC = {x : C(x) ≥ |x|} is a set of Kolmogorov-random strings. How can I show that RC is co-re I have been reading this paper What Can be Efficiently Reduced to the Kolmogorov-Random Strings? which just says that we know that by Kum96 we know that RC is Co-re I was not […]

Solving recurrences of the form $T(n) = aT(n/a) + \Theta(n \log_2 a)$

The time complexity for the merge sort algorithm is $T(n) = 2T(n/2)+\Theta(n)$, and the solution to this recurrence is $\Theta(n\lg n)$. However; assume you are not dividing the array in half for sorting, but instead in, say, $a$ pieces. Then the time would be something like $T(n) = aT(n/a) + \Theta(n \log_2 a)$. (The last […]

A one-tape Turing machine which operates in linear time can only recognize a regular language

Show that A one-tape Turing machine which operates in linear time can only recognize a regular language I have no idea how to solve it. Can you give me show how to solve it ? I am beginner at this subject so I ask for an indulgence.

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 consecutive primes is the only information to work off of. Also would Fermat’s factorization be an […]

Determining computational complexity of stochastic processes

I have an program which implements a Markov chain Monte Carlo process on a system of N bits, stopping when the process converges. Let’s use T to denote the average number of steps made by the Markov chain before convergence. I want to know how T scales with N. Specifically I’d like to know whether […]

Test symmetricity for a sparse matrix

I have a sparse matrix in LIL (List of Lists) format. I want to test whether the matrix is symmetric or not. Let’s say I have n non-default elements. What’s the best complexity in terms or space and time I can achieve? The best solution I have came up with so far is to traverse […]

Time Complexity of $T(n)=T(n-2)+\frac{1}{\log(n)}$

Solve $T(n)=T(n-2)+\frac{1}{\log(n)}$ for $T(n)$. I am getting the answer as $O(n)$ by treating $1/\log(n)$ as $O(1)$. The recursive call tree of this is a lop-sided tree of height $n$. Hence, considering the amount of work done in each step, the answer comes out to be $O(n)$. Please verify my answer, and tell me if I […]