Questions tagged [linear-complexity]

The tag has no usage guidance.

4 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
0answers
358 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
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-...
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
79 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 ...