An algorithm is said to have complexity O log^4 (n) . On a trial run, in ten sec

Question

An algorithm is said to have complexity O log^4 (n) .

On a trial run, in ten seconds it executes for an input of n = 128. Suppose we want to let it run “overnight” (lets say the night is 8 hours long, i.e. 28,800 seconds), what input (i.e. approximate value of n) should we supply?

Suppose we carry out a linear (sequential) search of an unordered list L with n items. We are looking for an object X which occurs exactly once in the list, and we start our search from the left of the list. The probability that the object is at any given position is not uniform: Rather it is given by the function Prob.(X is at position i) = (2i /n(n + 1)). Determine the average number of comparisons we must make to find X. (In your analysis here, you may need to make use of the fact that the sums of the squares of the first n natural numbers is n(n + 1)(2n + 1)/6.)

(c) If one were to carry out the linear search described in (b) in reverse order (i.e. starting from the right), determine again the average number of comparisons

Explanation / Answer

As per chegg guidelines,i'm solving only one.please repost other questions

Assumption: By log4(n), you mean it is log n to the base 4 andnot log n to the power 4.
for n = 128, the time taken i.e. 10 sec = O(log4(n)) i.e.

10 = k * log4(128) + c, we can ignore the constant
=> 10 = k * log4(128) = > 10 = k*7/2
=> k = 20/7

Now,
28800 = k*log4(n)
=> 28800 = 20/7 * log4(n)
=> log4(n) = 28800*7/20 = 10080
n = 4^10080

Please give Thumbs up,if it helped you :)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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