5) You wish to perform a daily re-sorting of the most visited student websites f

Question

5) You wish to perform a daily re-sorting of the most visited student websites from CS251. You are allowed to consider the following approaches (in all of them n is the number of students): Approach A) If you assume that the popularity of the websites among students do not change much from day to day, you can implement an O(n) average running time algorithm to keep the website popularity sorted in daily manner (n is the number of students who search the website on that day). This algorithm costs 100 time units per step to perform Approach B) If you ignore the assumption of constant popularity, you can be provided with an 0(n2) sorting algorithm to keep the website popularity sorted in daily manner(based on the search of student on that day) but we do not know the cost of this algorithm per unit. However, we know that 20 students are registered to CS251 Approach C) Assume you are provided with an O(n log(n)) sorting algorithm and this algorithm costs 50 time units per step to perform Note: Base of the logarithm is 10 for all the calculations. 5-1) What should be the cost per time unit for Approach B so it takes the same amount of time as Approach A? b. 5 C. 100 d. 2000 5-2) How many students should register to CS251 so Approaches A and C take the same amount of time? a. 20 b. 50 C. 100 d. 200

Explanation / Answer

well this question is simple maths with some assumptions.

first let me explain this O(n) notation:

this means that for n students the algorithm will take linear time.

In calculations we will use O(n)=n for simplicity.

now :

5-1).

100 . O(n) = x . O(n2)

we need to find X.

so, 100 n = x . n2 where n=20

therefore

2000 = x . 400 so answer is 5.

5-2).

100 . O(n) = 50 . O(nlogn)

simplifying

2 . n = n . logn

cancelling n from both sides

2 = log n

now base of log is 10

threrfore the answer is n = 10 2. so n=100

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

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