{"id":26423,"date":"2017-10-26T21:59:21","date_gmt":"2017-10-26T16:29:21","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26423"},"modified":"2017-10-26T21:59:21","modified_gmt":"2017-10-26T16:29:21","slug":"randomized-algorithms-set-1-introduction-analysis-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/randomized-algorithms-set-1-introduction-analysis-2\/","title":{"rendered":"Randomized Algorithms | Set 1 (Introduction and Analysis)"},"content":{"rendered":"
\n

Randomized Algorithms | Set 1 (Introduction and Analysis)<\/h1>\n<\/header>\n
\n

What is a Randomized Algorithm?<\/strong><\/h2>\n

An algorithm that uses random numbers to decide what to do next anywhere in its logic is called Randomized Algorithm.. For example, in Randomized Quick Sort, we use random number to pick the next pivot (or we randomly shuffle the array). And in Karger\u2019s algorithm<\/a>, we randomly pick an edge.<\/p>\n

How to analyse Randomized Algorithms?<\/strong><\/h2>\n

Some randomized algorithms have deterministic time complexity. For example, this<\/a> implementation of Karger\u2019s algorithm has time complexity as O(E). Such algorithms are called Monte Carlo Algorithms<\/a> and are easier to analyse for worst case.
\nOn the other hand, time complexity of other randomized algorithms (other than Las Vegas) is dependent on value of random variable. Such Randomized algorithms are called Las Vegas Algorithms<\/a>. These algorithms are typically analysed for expected worst case. To compute expected time taken in worst case, all possible values of the used random variable needs to be considered in worst case and time taken by every possible value needs to be evaluated. Average of all evaluated times is the expected worst case time complexity. Below facts are generally helpful in analysis os such algorithms.
\nLinearity of Expectation<\/a>
\nExpected Number of Trials until Success.<\/a><\/p>\n

For example consider below a randomized version of QuickSort.<\/p>\n[ad type=”banner”]\n

A Central Pivot<\/strong> is a pivot that divides the array in such a way that one side has at-least 1\/4 elements.<\/p>\n

\/\/ Sorts an array arr[low..high]\r\nrandQuickSort(arr[], low, high)<\/strong>\r\n\r\n1.<\/strong> If low >= high, then EXIT.\r\n\r\n2.<\/strong> While pivot 'x' is not a Central Pivot.\r\n  (i)   Choose uniformly at random a number from [low..high]. \r\n        Let the randomly picked number number be x<\/strong>.\r\n  (ii)  Count elements in arr[low..high] that are smaller \r\n        than arr[x]. Let this count be sc<\/strong>.\r\n  (iii) Count elements in arr[low..high] that are greater \r\n        than arr[x]. Let this count be gc<\/strong>.\r\n  (iv)  Let n<\/strong> = (high-low+1). If sc >= n\/4 and\r\n        gc >= n\/4, then x is a central pivot.\r\n\r\n3. <\/strong>Partition arr[low..high] around the pivot x.\r\n\r\n4. <\/strong>\/\/ Recur for smaller elements\r\n   randQuickSort(arr, low, sc-1) \r\n\r\n5.<\/strong> \/\/ Recur for greater elements\r\n   randQuickSort(arr, high-gc+1, high)<\/pre>\n
The important thing in our analysis is, time taken by step 2 is O(n).<\/p>\n
How many times while loop runs before finding a central pivot?<\/strong>
\nThe probability that the randomly chosen element is central pivot is 1\/2.<\/p>\n
Therefore, expected number of times the while loop runs is 2 (See this<\/a> for details)<\/p>\n
Thus, the expected time complexity of step 2 is O(n).<\/p>\n
What is overall Time Complexity in Worst Case?<\/strong>
\nIn worst case, each partition divides array such that one side has n\/4 elements and other side has 3n\/4 elements. The worst case height of recursion tree is Log 3\/4<\/sub> n which is O(Log n).<\/p>\n
T(n) < T(n\/4) + T(3n\/4) + O(n)\r\nT(n) < 2T(3n\/4) + O(n)\r\n\r\nSolution of above recurrence is O(n Log n)<\/pre>\n<\/div>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Randomized Algorithms | Set 1 (Introduction and Analysis) – Randomized Algorithms An algorithm that uses random numbers to decide what to do next.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,77748],"tags":[78696,78685,78692,78695,78694,78693,78684,78683],"class_list":["post-26423","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-randomized-algorithms","tag-application-of-randomized-algorithm","tag-las-vegas-randomized-algorithm","tag-randomized-algorithm-definition","tag-randomized-algorithms-lecture-notes","tag-randomized-algorithms-pdf","tag-randomized-quicksort-complexity","tag-randomized-quicksort-in-c","tag-types-of-randomized-algorithms"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26423","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26423"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26423\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26423"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26423"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26423"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}