New answers tagged

0 votes

Is there a defined set of steps or principles on how to reduce time complexity of algorithms?

A systematic approach is to start with Brute Force and then Keep thinking what is unnecessary or repeated, try to eliminate those steps... many times it's not so obvious and which is why it is ...
  • 1
2 votes
Accepted

Counting integers $n \leq x$ with a given prime signature

Here is a complicated approach that might offer a modest improvement for values of $x$ of the size mentioned in your comment, when you want to compute $C(S,x)$ for many different $S$ and the same $x$: ...
  • 145k
1 vote

In merge sort, what will be the time complexity if in each recursion, we break the array in two parts of size 1/4 and 3/4 respectively?

Let $c \in (0, \frac{1}{2}]$ be any constant. In your case $c = \frac{1}{4}$. If, at a generic recursive call, you partition the $n$ elements in your input array into a subarray of size $cn$ and ...
  • 24.5k
0 votes

Best known deterministic algorithm for generation of any (non random) n-bit prime?

In practice, you should absolutely use a randomized algorithm. There is no reason in practice to use a deterministic algorithm, or to care about the complexity of deterministic algorithms. So I will ...
  • 145k
1 vote

Show that $TIME(\sqrt{n})$ = $TIME(1)$

Suppose that a Turing machine runs in time at most $T(n)$ on inputs of length $n$, where $T(n) = o(n)$. Therefore $\lim_{n\to\infty} T(n)/n = 0$, and so we can find $N$ such that $T(n) < n$ for $n \...
1 vote
Accepted

Is there a possibility to convert the following problem into divide and connquer

We can note that to compute $C_{ij}$, it is enough to know the sum, and the count of $\{b_{jk}\}_{k=1}^n$ such that $b_{jk} < a_{ij}$. This can be done after a simple preprocessing and the final ...
  • 51
1 vote

Sieve of Eratosthenes for factorization: bitwise complexity?

Newer multiplication algorithms aren't needed to show such a time bound in this model. Given a precomputed multiplication table of size $O(p)$, multiplication $a \times b$ of $a, b \leq p^{O(1)}$ ...
  • 1,511
4 votes
Accepted

Optimal algorithmic complexity of "a nonrepetitive stack"?

Kosolobov [1] solved this exact problem. The first algorithm in the paper supports stack operations on a string while detecting a repeated substring, and each operation takes amortized $O(\log m)$ ...
  • 1,511
2 votes
Accepted

Improving an algorithm involving two pairs of sums

It's trivial to do in $O(n^3)$ time, by enumerating all $O(n^3)$ tuples $(j,k,j',k')$ such that $j+k=j'+k'$, computing the appropriate product, and summing those products. I'll let you discover how ...
  • 145k
2 votes

Can an algorithm decide whether any DFA accepts an infinite language? What is its time complexity?

In addition to the answers linked by Rinkesh P. in a comment, here is an approach that directly translates into an efficient algorithm. The DFA accept an infinite language if and only if there is a ...
  • 24.5k
-1 votes

Automatic differentiation - Upper bound time

Proof can be found in section 4.4 and 4.5 of "evaluating derivatives and principles of algorithmic differentiation" from Griewank&Walther
  • 109
1 vote

Is there a faster than O(n^2) way to compute a vector of length n from another vector and an n by n matrix?

While the worst-case complexity is $O(n^2)$, the following special case might be of interest for some applications of this algorithm: If: $B$ does not contain negative values and: $a_i = 0$ Then $...
10 votes

Is there a faster than O(n^2) way to compute a vector of length n from another vector and an n by n matrix?

A key observation is that if $i$-problems are completely independent, you need to compute $n$ sums of the form $$s=\sum_{j=1}^n\max(0,a-b_j).$$ With $a=0$ and all $b_j<0$, we get the even simpler ...
  • 5,283
30 votes
Accepted

Is there a faster than O(n^2) way to compute a vector of length n from another vector and an n by n matrix?

That's not possible. You have to read in the entire $B$ matrix to determine the correct answer, which fundamentally requires $O(n^2)$ time.
  • 145k
1 vote
Accepted

Algorithm to optimise the cost to choose a subset of array

This is the (weighted) set cover problem. It is NP-hard, so there is not likely to be any efficient algorithm that works on all problem instances. There are various methods to deal with this: e.g., ...
  • 145k
0 votes

Is it possible to compute an equality hash for nodes in a *cyclic* directed graph in less than quadratic time?

Directed Graph Hashing (Helbling 2020) described a method of structural hashing cyclic directed graphs. If I understand it correctly, first it reduces the graph to the condensation graph in which ...
2 votes

Can we create a decision tree for any comparison sorting algorithm even if it is very complicated?

The procedure below can be used to explicitly build the decision tree of any comparison-based algorithm: generate all permutations of the array $[1, 2, \cdots n]$. for every permutation, run the ...
  • 5,283
1 vote

Can we create a decision tree for any comparison sorting algorithm even if it is very complicated?

In theory, yes you should be able to create a decision tree for every comparison based sorting algorithm. You can write a program that will do so (for a fixed comparison-based sorting algorithm of ...
  • 313
1 vote
Accepted

Can we create a decision tree for any comparison sorting algorithm even if it is very complicated?

In general, a decision tree would enumerate all possible permutations $(N!)$ for given input of $N$ elements, out of which only $1$ would be desirable. A sorting algorithm doesn't generate all ...
  • 539
0 votes

How to find average time complexity of backtracking algorithm?

First run your algorithm, count the iterations. Check how it varies with different inputs. Get some idea about the runtime. Unless you have a good counter argument, backtracking tends to be ...
  • 25.9k
0 votes
Accepted

Time complexity analysis for Searching in a Hash table

Let $\alpha = \frac{n}{m}\ $ where $n$ = total no. of elements in hashtable ,$m$ = number of slots in hashtable, be the load factor or Average number of elements in a chain. Given that each chain is ...
  • 539
0 votes

How to find the runtime out of a recursion formula when using divide and conquer

Hints: You can guess this information from the equation itself. In $T(n)$, $n$ denotes the size of the problems. So in $T\left(\dfrac nb\right)$, $\dfrac nb$ must be the size of the subproblems. Now ...
  • 5,283
1 vote
Accepted

How to find the runtime out of a recursion formula when using divide and conquer

Your example is a bit weird, because you are not describing a problem you are trying to solve for a given length $n$… For the explaination, suppose you want to count the number of ships (like in ...
  • 7,568
0 votes

I need help finding the complexity of an algorithm

No, the complexity cannot be constant, because the iterations $j = 2^j$ always yield a finite integer, and there is always a larger $n$. So the number of iterations is unbounded. Anyway, as the ...
  • 5,283
4 votes
Accepted

Combining fork() and algorithms

Can we combine these two to give an algorithm that betters the usual Time complexity? The key to your question is "what do you mean by time complexity?" Often it is quite clear, and we don'...
  • 3,150
2 votes

Combining fork() and algorithms

Many divide-and-conquer algorithms are actually implemented sequentially, and the idea of working on each half "in parallel" is more to help with conceptual understanding than an actual ...
  • 145k
0 votes

what will be the time complexity of the following procedure?

When flag is true, the body of the third for takes time ak²+b; otherwise it takes c. So the total running time is ...
  • 5,283
1 vote
Accepted

Set of Turing machines that accepts at least one input in bounded time

Your reasoning is wrong because you assert something without proof. You just assert that the only way to do it is to try all $x$, but there is no justification given for this assertion, and we don't ...
  • 145k
1 vote

Running time of SAT and other EXPTIME algorithms

You have the definition of EXPTIME wrong. The definition refers to the length of the input. Neither $s$ nor $n$ are the length of the input. The definition of EXPTIME says that the running time is $...
  • 145k
0 votes

translating operations per second (OPS) to floating point operations per second (FLOPS)

If you don't care too much about accuracy, FLOPS and OPS are roughly equivalent. If you do care, then neither FLOPS nor OPS are precise enough.
  • 5,283
3 votes

A solution with O(n) time complexity is always slower than a solution with O(nlog(n)) time complexity even though they have the same space complexity

The big O time notation is a way to talk about relative time behavior of different algorithms as n approaches infinity. Shooting towards infinity is a trick that allows us to ignore the constant parts ...
  • 131
1 vote

translating operations per second (OPS) to floating point operations per second (FLOPS)

Processors without built-in floating point arithmetic usually require say 50 non-floating point operations to implement a floating point operations. Processors with built-in floating point arithmetic ...
  • 25.9k
5 votes

A solution with O(n) time complexity is always slower than a solution with O(nlog(n)) time complexity even though they have the same space complexity

One solution will run in time up to $c_1 n log n$ for some constant $c_1$ if n is large enough. The other solution will run in time up to $c_2 n$ for some $c_2$ is n is large enough. So you have three ...
  • 25.9k
2 votes

A solution with O(n) time complexity is always slower than a solution with O(nlog(n)) time complexity even though they have the same space complexity

A likely explanation is the hidden constant. We can assume the following empirical formulas for the running times: c.n.log(n) and d.n. Then it is possible that c.log(200000) < d, for instance due ...
  • 5,283

Top 50 recent answers are included