Questions tagged [linear-complexity]
The linear-complexity tag has no usage guidance.
14
questions
0
votes
1
answer
45
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
1
answer
26
views
number of substrings in same position with same contents
L1 and L2 are two lists which only consist of X's and Y'...
- 13
1
vote
2
answers
271
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 ...
- 229
0
votes
1
answer
38
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
0
votes
1
answer
63
views
Show that $\text{BOOL-VAL}$ and $\text{DNF-SAT}$ is decidable in linear time
A boolean expression is valid if it is true for every valuation. The problem
$\text{BOOL-VAL}$ asks whether a given boolean expression is valid. As the question suggests I need to show that $\text{...
user153634
0
votes
2
answers
254
views
Finding minimal amount of coins to reach n
According to my syllabus, this is a dynamic programming problem yet the explanation to the problem I’m supplied with is really confusing and not close to being understandable.
The problem is such:
You ...
- 315
1
vote
1
answer
180
views
Limited tapes-version TM for pair sum
In the problem of pair-sum we are given a multiset $A$ and a number $\alpha$. We are asked to find whether there is a pair ($2$ numbers) of $A$ s.t. their sum is $\alpha$. Here all numbers are small/...
- 125
-2
votes
3
answers
120
views
Is O(k*n) in this case linear?
Problem: find sum of k element in array and it is biggest?
time complexity of my algorithm is O(k*n).Is it linear complexity?
- 11
0
votes
2
answers
122
views
Find distinict elements in an array in $O(n)$ time
Given this pseudo-code that finds the number of distinct elements in the given array:
...
- 29
19
votes
3
answers
7k
views
Time complexity $O(m+n)$ Vs $O(n)$
Consider this algorithm iterating over $2$ arrays $(A$ and $B)$
size of $ A = n$
size of $ B = m$
Please note that $m \leq n$
The algorithm is as follows
...
- 291
0
votes
0
answers
62
views
In-place linear sort of integers, again
I am amazed by the many discussion regarding the existence of any linear and in-place sorting algorithm, and variants, see e.g.
is-this-implementation-of-bucket-sort-considered-in-place
is-counting-...
- 623
8
votes
0
answers
414
views
Shortest path that can be split into contiguous segments of 5 edges connecting 6 distinct nodes in an unweighted graph
The following problem (I'm paraphrasing) appeared in the 2019 Balkan Olympiad in Informatics:
Five friends are on a road trip in a country with $N$ cities and $M$ bidirectional roads joining them. ...
- 121
0
votes
0
answers
395
views
How do I calculate the average number of comparisons for linear search?
In a list of 15 entries (city names) if searching for a particular name what is the average number of comparisons using linear search? Worst case it would 15 comparisons and best case it would be 1 ...
- 101
2
votes
2
answers
237
views
Finding the most frequent element assuming $\Theta(n)$ frequency
We know [Ben-Or 1983] that deciding whether all elements in an array are distinct requires $\Theta(n \log(n))$ time; and this problem reduces to finding the most frequent element, so it takes $\Theta(...
- 955