• Welcome To Perfect Grade
Order Now

Mathematical induction

  • April 9, 2021
  • Manyara2021
  • 27

 
1. Use mathematical induction to show that when n is a power of 2, T(n) = n lg n is the
solution of the recurrence relation
T(n) = (
2 if n = 2
2 · T(
n
2
) + n if n = 2k
for k > 1.
2. Suppose we are comparing implementations of Insert-sort and Merge-sort on
the same machine. For input of size n = 2k
for k ≥ 1, Insert-sort runs in 8n
2
comparisons, while Merge-sort runs in 64n lg n comparisons. For which value of n
does Insert-sort beat Merge-sort?
3. We can express Insert-sort as a recursive procedure as follows. In order to sort
A[1…n], we recursively sort A[1…n−1] and then insert A[n] into sorted array A[1…n−
1].
(a) Write the pseudocode for this recursive version of Insert-sort, name it Insertsort-recur.
(b) Write a recurrence for the running time of of Insert-sort-recur.
(c) Find the solution of the recurrence relation in (b).
(d) Is Insert-sort-recur more expensive than Insert-sort?
4. Given an array s = hs[1], s[2], . . . , s[n]i, and n = 2d
for some d ≥ 1. We want to find
the minimum and maximum values in s. We do this by comparing elements of s.
(a) The “obvious” algorithm makes 2n − 2 comparisons. Explain.
(b) Can we do it better? Specify a divide-and-conquer algorithm.
(c) Let T(n) = the number of comparisons your divide-and-conquer algorithm makes.
Write a recurrence relation for T(n).
(d) Show that your recurrence relation has as its solution T(n) = 3
2
n − 2.
5. Let S be an array of n integers such that S[1] < S[2] < · · · < S[n]. (1) Specify
an O(lg n) algorithm which either finds an i ∈ {1, 2, . . . n} such that S[i] = i or else
determine that there is no such i. (2) Justify the correctness and running time of your
algorithm.
 

Tags:

27 comments on “Mathematical induction”

  8. Pingback: relx คืออะไร
  23. Pingback: โซล่าเซลล์

  24. онлайн казино brillx сайт
    brillx официальный сайт
    Брилкс Казино – это небывалая возможность погрузиться в атмосферу роскоши и азарта. Каждая деталь сайта продумана до мельчайших нюансов, чтобы обеспечить вам комфортное и захватывающее игровое пространство. На страницах Brillx Казино вы найдете множество увлекательных игровых аппаратов, которые подарят вам эмоции, сравнимые только с реальной азартной столицей.Brillx Казино — это место, где сливаются воедино элегантность и бесконечные возможности. Необычная комбинация азартных игр и роскошной атмосферы позволит вам окунуться в мир бриллиантового веселья. Наше бриллиантовое казино уверенно входит в число лидеров азартной индустрии, и в этом году мы готовы порадовать вас еще большим разнообразием игр и выигрышей.

  25. Pingback: Golden rule microdose

  26. Hi, i think that i saw you visited my weblog so i came to “return the favor”.I am attempting to find
    things to improve my web site!I suppose its ok to use some of your ideas!!

  27. Pingback: retinerea noxelor

Leave a Reply

Your email address will not be published. Required fields are marked *