# Questions tagged [linear-complexity]

The tag has no usage guidance.

7 questions
Filter by
Sorted by
Tagged with
70 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: ...
3k 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 ...
41 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-...
349 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. ...
34 views

### Boruvka in planar graphs

On wikipedia it says that boruvka can be implemented in linear time for planar graphs, but I don't know how to prove that.
### 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(...