CODEWITHSUNDEEP
algorithmcomplexity-theory
user1062704
user1062704

Reputation: 448

Average case complexity - calculation for linear algorithm

Just a quick question:

If I have a linear search algorithm (which will go through every element once up to a certain condition), how can I calculate the average case complexity for n = 500? The worst case and best case is easy.

Upvotes: 0

Views: 1687

Answers (2)

wasim sofi
wasim sofi

Reputation: 27

The average case complexity of a linear search algorithm is n+2 where n is the number of elements in the list.

Upvotes: 0

tfinniga
tfinniga

Reputation: 6849

The average case is similarly simple: as long as the items you're finding are unique, on average you will have to look halfway through the list + 0.5.

Let's assume that you look up every item in the list once. When you look up the first item, you will have to inspect 1 item. When you look up the second item, you will have to inspect 2 items, and so forth. The total number of inspections is

1 + 2 + 3 + ... + 500 = 125250

So with 500 lookups, you will total 125250 items inspected. On average, that is 250.5 inspections per lookup.

If your lookup patterns are nonuniform then that will skew your average case (for example, if you look up items at the beginning of the list more often, or if some items are repeated and finding any of them is sufficient)

Upvotes: 3

Related Questions