Skip to main content

Questions tagged [linear-complexity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
2 answers
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 ...
Zirui Wang's user avatar
1 vote
1 answer
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 ...
Lorenzo's user avatar
  • 11
0 votes
1 answer
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 ...
donaastor's user avatar
  • 101
1 vote
1 answer
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'...
20389642219's user avatar
1 vote
2 answers
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 ...
Yarin's user avatar
  • 275
0 votes
1 answer
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'...
emacos's user avatar
  • 121
0 votes
1 answer
93 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{...
user avatar
0 votes
2 answers
369 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 ...
Aishgadol's user avatar
  • 355
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/...
Benicio Agüero's user avatar
-2 votes
3 answers
173 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?
Canucnuong's user avatar
0 votes
2 answers
130 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: ...
Omri Braha's user avatar
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 ...
Shylajhaa's user avatar
  • 291
0 votes
0 answers
96 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-...
Matthieu Latapy's user avatar
8 votes
0 answers
418 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. ...
Andi Qu's user avatar
  • 221
0 votes
0 answers
467 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 ...
martinbshp's user avatar
2 votes
2 answers
254 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(...
einpoklum's user avatar
  • 975