Assume that a particular web application looks up subscribers when they log in.

Question

Assume that a particular web application looks up subscribers when they log in. Assume that 1/10 of the subscribers login on a given day. If there are 50,000 subscribers how many lookups are there each day?
Assume that this particular web application uses a linear search to do the lookups. On the average, how many array elements are examined in order to process the logins over the course of one day?
Suppose this web application becomes popular and the number of subscribers doubles to 100,000. Now, on the average, how many array elements are examined in order to process the logins over the course of one day?
So with a linear search algorithm, when the number of lookups is proportional to the number of subscribers, then when the number of subscribers doubles, the number of elements that must be examined increases by a factor of

Explanation / Answer

Assume that a particular web application looks up subscribers when they log in. Assume that 1/10 of the subscribers login on a given day. If there are 50,000 subscribers how many lookups are there each day?

1/10 * 50k = 5000 lookups (for those who try to login)

Assume that this particular web application uses a linear search to do the lookups. On the average, how many array elements are examined in order to process the logins over the course of one day?

OK, I don't know what they mean by average here. Usually complexity problems are solved in worst case scenario:

1. on Each lookup, worst thing that can happen is that we find our result in the last element, so we scan all though the array: 50000 checks
2. If we do it for each lookup: 5000 * 50000 = 250,000,000

If they, by average, mean the fact that our chances of finding our seult at any given index are the same (uniform distribution) then we would on average find it in the middle: 25000 checks
Total: 5000 * 25000 = 125,000,000

Suppose this web application becomes popular and the number of subscribers doubles to 100,000. Now, on the average, how many array elements are examined in order to process the logins over the course of one day?

well, in both cases it grows by a factor of 2, so either 500,000,000 in worst case or 250,000,000 in average

So with a linear search algorithm, when the number of lookups is proportional to the number of subscribers, then when the number of subscribers doubles, the number of elements that must be examined increases by a factor of TWO (2)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.