Questions tagged [linear-complexity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
17 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
32 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(...