{"id":97266,"date":"2017-10-23T07:00:00","date_gmt":"2017-10-23T21:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/?p=97266"},"modified":"2019-03-13T01:19:15","modified_gmt":"2019-03-13T08:19:15","slug":"20171023-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20171023-00\/?p=97266\/","title":{"rendered":"A closer look at the complexity analysis of finding the k’th smallest element in two sorted arrays"},"content":{"rendered":"

Given two sorted arrays of the same length, with unique elements, find the k<\/var>th smallest element in the combined collection. One solution involves the double binary search<\/a>. I’ll let you go read the article to see how it works. I’m here to dissect the complexity analysis. <\/p>\n

Since every time we remove ¼ elements, the complexity is O<\/var>(2*log(N<\/var>))<\/span>, i.e.<\/i>, O<\/var>(log(N<\/var>))<\/span>. <\/p><\/blockquote>\n

Okay, that was pretty glib. How did we get there? <\/p>\n

If an algorithm reduces the problem to a smaller problem that is half the size, then the number of reduction steps needed to reduce the problem to size 1 is ⌈lg N<\/var>⌉<\/span>. More generally, if you have an algorithm where the ratio of the size of the next iteration to the size of the current iteration is r<\/var>, then the number of reduction steps is ⌈log1\/r<\/var><\/sub> N⌉<\/span>. <\/p>\n

In the above example, the ratio is r<\/var> = ¾, so the number of reduction steps is ⌈log4\/3<\/sub> N<\/var>⌉<\/span>. We can change the logarithm to base 2<\/a> to arrive at ⌈(lg N<\/var>)÷(lg (4\/3))⌉<\/span> ≈ ⌈2.4 × lg N<\/var>⌉<\/span>. <\/p>\n

This is not the same as 2 × lg N<\/var><\/span> given in the original article. My guess is that the original article calculated the conversion factor incorrectly as lg 4<\/span> = 2. <\/p>\n

But since this is all for order of magnitude calculations, an error in the constant factor is forgiven because order of magnitude ignores constant factors. <\/p>\n

But wait, does the formula even apply in the first place? <\/p>\n

The formula applies if the reduced problem is the same as the original problem, but with a smaller size. In the case under consideration, the starting point was two equal-sized arrays, but when we’re done, we have two unequal-sized arrays: One of the arrays shrunk in half, but the other stayed the same size. <\/p>\n

We used the wrong formula! <\/p>\n

Consider the second iteration, where we have one small array and one large array. And suppose the second iteration of the algorithm decides to throw away half of the smaller array. We did not throw away a quarter of the elements. We threw away half of the smaller array, which is one third of the total number of elements, which means that we threw away only a sixth! <\/p>\n

It gets worse at the third iteration: If we are unlucky and the algorithm decides to throw away half of the tiny array, we discarded only one tenth of the elements. <\/p>\n

So in the worst case, we get into a case of diminishing returns, where were throw away less and less from the small array and never make a dent in the big array. Does this algorithm even guarantee termination? <\/p>\n

In mathematics, sometimes the way to solve a problem is to convert it to a harder problem, and then solve the harder problem. In this case, the harder problem is “Given two sorted arrays of possibly-unequal length<\/i>, with unique elements, find the k<\/var>th smallest element in the combined collection.” <\/p>\n

Let f<\/var>(n<\/var>, m<\/var>)<\/span> represent the number of reduction steps needed to solve the problem, where n<\/var> and m<\/var> are the lengths of the two arrays. If you decide to throw away half of the first array, then the number of remaining steps is f<\/var>(½n<\/var>, m<\/var>)<\/span>. Similarly, if you decide to throw away half of the second array, then the number of remaining steps is f<\/var>(n<\/var>, ½m<\/var>)<\/span>. You now have the recursion f<\/var>(n<\/var>, m<\/var>) = 1 + max(f<\/var>(½n<\/var>, m<\/var>), f<\/var>(n<\/var>, ½m<\/var>))<\/span>. <\/p>\n

The solution to this recursion is f<\/var>(n<\/var>, m<\/var>) = ⌈lg n<\/var>⌉ + ⌈lg m<\/var>⌉<\/span>. <\/p>\n

You can think of the problem this way: You have two arrays, and based on the algorithm, you cut one in half or you cut the other in half, until both arrays are cut down to just one element. It takes ⌈lg n<\/var>⌉<\/span> cuts to reduce the first array and ⌈lg m<\/var>⌉<\/span> cuts to reduce the second array. The algorithm tells you which piece to cut next, but regardless of what order the algorithm gives, the total number of cuts is the same. <\/p>\n

In the original problem, n<\/var> = m<\/var> = ½N<\/var><\/span>. Therefore, the number of reduction steps is ⌈lg ½N<\/var>⌉ + ⌈lg ½N<\/var>⌉ = 2⌈lg ½N<\/var>⌉ = 2⌈lg N<\/var>⌉ – 2<\/span>, which is O<\/var>(lg N<\/var>)<\/span>. <\/p>\n

So the answer given in the article was off by two. This doesn’t make any difference when calculating order of magnitude, but it was interesting that the incorrect calculation was so close to the correct one. <\/p>\n","protected":false},"excerpt":{"rendered":"

Let’s calculate it properly.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-97266","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"

Let’s calculate it properly.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/97266","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=97266"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/97266\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=97266"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=97266"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=97266"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}