0

# What is linearity problems?

Wiki User

2017-01-02 09:32:15

The linear search problem relates to searching an un-ordered sequence. Because the data is no ordered, we must start at one end of the sequence and inspect each element in turn tunil we find the value we are looking for. If we reach the one-past-the-end of the sequence, the value does not exist. From this we can see that for a set of n elements, the worst case (the element does not exist) is O(n) time while the best case is O(1) time (the element we seek is the first element). Given that there is a 50/50 chance the element we seek will be closer to the start of the sequence than the end, the average seek time is O(n/2).

When a set is ordered we can reduce search times by starting in the middle of the set. In this way, if the element is not found we can eliminate half of the set because we know which half contains the value (if it exists). We repeat the process until we find the value in the middle of the remaining set or the remaining set is empty. The end result is that search times are reduced to a worst case of O(log n), the binary logarithm of n.

Mara Denesik

Lvl 10
2021-11-29 09:38:20
🙏
0
🤨
0
😮
0
Study guides

20 cards

➡️
See all cards
3.7
323 Reviews