{"id":336,"date":"2010-04-15T20:19:53","date_gmt":"2010-04-16T03:19:53","guid":{"rendered":"http:\/\/www.glencora.org\/?p=336"},"modified":"2010-04-15T20:19:53","modified_gmt":"2010-04-16T03:19:53","slug":"adaptive-analysis","status":"publish","type":"post","link":"https:\/\/blogs.oregonstate.edu\/glencora\/2010\/04\/15\/adaptive-analysis\/","title":{"rendered":"Adaptive analysis"},"content":{"rendered":"<p><img loading=\"lazy\" decoding=\"async\" class=\"alignright\" src=\"http:\/\/www.cs.uwaterloo.ca\/~jbarbay\/JyByes\/borne.png\" alt=\"Adaptive analysis\" width=\"256\" height=\"256\" \/><a href=\"http:\/\/www.dcc.uchile.cl\/~jbarbay\/\">J\u00e9r\u00e9my Barbay<\/a> was visiting me this week from <a href=\"http:\/\/www.uchile.cl\/\">Universidad de Chile<\/a>. \u00a0Although we overlapped at Waterloo by a few months, we had never talked in depth about research before. \u00a0His visit was great timing to scoop me out of some research doldrums after a stressful winter quarter. \u00a0He gave a great talk on adaptive analysis.<\/p>\n<p>As we all know, algorithms often out-perform their worst-case analysis. \u00a0There are a few theoretical tools for explaining this behaviour: think O(n log n) average case v. O(n^2) worst case for quick sort and poly-time smoothed analysis v. exponential-time worst case for the simplex algorithm. \u00a0In adaptive analysis, we analyze an algorithm in terms of some (problem-dependent) hardness parameter, h. \u00a0As an introductory example, consider insertion sort. \u00a0If the input array is sorted, insertion sort takes O(n) time. \u00a0If the input array is in reverse order, insertion sort takes O(n^2) time. \u00a0 If there are h pairs of elements that are mutually inverted, then insertion sort takes O(n+h) time: the running time depends on how hard a particular input instance is to sort.<\/p>\n<p>Adaptive analysis has appeared several times in the past, but the word <em>adaptive<\/em> might not have been used. \u00a0J\u00e9r\u00e9my would be a better person to provide a list. \u00a0The most common examples seem to involve the analysis of existing algorithms. \u00a0I would be most interested in the lens of adaptivity informing new algorithmic ideas, particularly those that would outperform existing algorithms, at least on interesting or useful inputs. \u00a0Is there a collection of examples of such results? \u00a0I know J\u00e9r\u00e9my mentioned one or two, but I&#8217;ve since forgotten in the whirlwind of whiteboard whimsy.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>J\u00e9r\u00e9my Barbay was visiting me this week from Universidad de Chile. \u00a0Although we overlapped at Waterloo by a few months, we had never talked in depth about research before. \u00a0His visit was great timing to scoop me out of some research doldrums after a stressful winter quarter. \u00a0He gave a great talk on adaptive analysis. [&hellip;]<\/p>\n","protected":false},"author":3747,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[106190,99446],"class_list":["post-336","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-tcs","tag-visitors"],"_links":{"self":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/336","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/users\/3747"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/comments?post=336"}],"version-history":[{"count":0,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/336\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/media?parent=336"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/categories?post=336"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/tags?post=336"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}