# Tag Info

## New answers tagged time-complexity

### 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 ...
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

### 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

### 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
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

### 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 ...

### 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

### 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
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

### 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

### 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
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

### 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

### 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

• 25.9k