Questions tagged [linear-complexity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
2answers
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: ...
18
votes
3answers
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 ...
0
votes
0answers
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-...
8
votes
0answers
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. ...
0
votes
0answers
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.
0
votes
0answers
69 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 ...
2
votes
2answers
101 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(...