# Questions tagged [linear-complexity]

The tag has no usage guidance.

16 questions
Filter by
Sorted by
Tagged with
92 views

### Is it possible to sort numbers in linear time and constant extra space?

The programming language is C++, and the elements of the input vector are of type int and able to take all valid ...
• 960
1 vote
89 views

### Sorting rational numbers in linear time

I am currently studying algorithms and computational complexity at University. I have recently got through three questions I found in an old exam: Is it possible to sort in asymptotically linear time ...
• 11
69 views

### Proving that this Huffman tree construction is valid

"Abstract": I have recently crafted a new algorithm for constructing code trees which I believe are optimal (the same thing that is constructed using Huffman's algorithm, at Wikipedia). It ...
• 101
1 vote
28 views

### number of substrings in same position with same contents

L1 and L2 are two lists which only consist of X's and Y'...
1 vote
537 views

### Algorithm for finding a path in a directed graph that visits each node in a given subset

I was wondering about a solution for the following problem: Given a directed graph $G=(V,E)$ and a subset of vertices $U \subseteq V$ suggest an algorithm that finds if there is a directed path that ...
• 275
39 views

### Design an algorithm with linear complexity

Let A[1 : n] be a vector of n integers such that all elements except O(n^2/3) elements are between 1 and 10n. Design an algorithm with linear complexity that sorts A. Beyond the algorithm, what I can'...
• 121