Top Down with Memorization Complexity

The purpose of this article is to analyze the complexity of algorithms written using a top down approach.

Most of the problems can inherently be described using top down recursion. The complexity of an algorithm, however, makes it far from usable in practical scenarios. This kind of algorithm shows exponential complexity and might need some kind of specialized solution to bring the hardness of the solution from exponential to polynomial complexity. To describe one such case, let's take the example of one moderate problem. The problem is as described below and is another variation of well known LCS (Longest common subsequence problem). The purpose of taking a problem with moderate complexity is to provide the audience with a challenge to come to a conclusion and work out a solution that is close enough for practical use. The problem is also different from what most of the readers have seen elsewhere. The problem is as given below.

A subsequence is palindromic if it is the same whether read left to right or right to left. For Instance, the sequence A;C; G; T; G; T;C; A; A; A; A; T;C;G has many palindromic subsequences, including A;C; G;C;A and A; A; A;A (on the other hand, the subsequence A;C; T is not palindromic). Devise an algorithm that takes a sequence x[1 : : : n] and returns the (length of the) longest palindromic subsequence. Its running time should be O(n2).

So as a layman programmer the problem seems to be recursive and solved with some recursive scheme. Let's call the Longest Palindrome Sequence as LPS. So given a string Aij, the solution is below.

                             Ai = Aj   --o  2 + LPS(i+1, j-1)
LPS(i, j) = Max
                            Ai != Aj   --o  Max(LPS(i, j-1), LPS( i+1, j))

The algorithm can easily be reproduced in any available language which supports recursion. So our naC/ve algorithm looks like

                   int LPS(i, j) {
                              If (Ai == Aj) {
                                    return 2 + LPS(i+1, j-1);
                              } else {
                                    return Max(LPS(i, j-1), LPS( i+1, j));
                              }
                   }

The solution by far looks correct. But can it be used practically for any good use? The exponential complexity of the above algorithm might even make it difficult for strings of moderate lengths. If we look closely at the solution we see the depth of the recursion increases exponentially. So given string of length k, the complexity of the above algorithm is 2 ^ k, since every problem is divided into 2 new problems. Worse, the same problem is repeating itself. So the total complexity in the worst case, when there is no palindrome in the problem string, is (2* 2 ^ K).

To make it more clear consider substring I, j. The problem I +1, j and I, j-1 has I + 1, j -1 common problems. Is there a way to avoid processing the same problems? Can we make use of computations, which we have already done? A minute's reflection will tell yes we could.

Below shows how we could do this. Read M as matrix in below code of length I, j.

                   int LPS(i, j) {
                        int lcs;
                        If (M[i][j] == -1) {
                              If (Ai == Aj) {
                                    lcs =  2 + LPS(i+1, j-1);
                              } else {
                                    lcs = return Max(LPS(i, j-1), LPS( i+1, j));
                              }
                              M[i][j] = lcs;
                        }
                        Return M[i][j];
                   }

The above algorithm is memoization and reduces the complexity of the problem by half. The above solution skips computing similar problems.

There is yet another solution to the above problem, which reduces the complexity to polynomial time. As most of us know it's a bottom up approach using Dynamic Programming.

The solution is given below and self explanatory. M is matrix where we store results for previous computations.

F           Mk,I   o   Ak  != Ai o    Mk,i-1      
     i = 0, n                           Ak  =  Ai o   2 + Mk+1, i-1
     j = 0, i
     k = j, i

Read F as for each. For the above algorithm the complexity is n ^ 3. The table is constructed bottom up. For ex A0, A0..Aj, A0 - An. So if you know Mi, j-1 you know M I, j. Do we need more explanation to code above thing? I guess not.

The complexity can further be reduced to n ^ 2 if we reverse the same string and run LCS over the two strings. Since complexity of LCS (Largest common ancestor is n ^ 2).



Related Articles

Comments

  • Cheap Oakley Jupiter Squared no tax worldwide

    Posted by sbedoxipi on 07/07/2013 07:36am

    FakE OaklEy SunglaSSES ,Oakley sunglasses lens sunglasses sale silver announcement is a milestone in the glasses. This new label of sunglasses provides you with an unprecedented enjoyment and fitness. Today, besides the bright colors and unusual shapes of persistent organic pollutants, greater eye-catching image of stylish glasses will be more defined than in the past. Today, the idea of Oakley sunglasses has occurred a fundamental change, because such glasses to be a fashion accessory than anything else. Cheap Oakley Antix ,Choice problems, you can get benefits. Find the specific model of sunglasses to decide on a model, it can be suitable for the specified amount of your taste and personality. Oakley sunglasses rights PLZ visit our wholesale Oakley sunglasses, Oakley sunglasses, lifestyle, blue, yellow harvest. Sunglasses every selection of kind of 1 color, even though ancient sunglasses name 's all set, nevertheless the eyes from the first factor. The sunglasses, the application of time, based on your usage habits, however, a lot of friends wearing sunglasses too casual and doesn't attach importance towards the upkeep of the sunglasses. Fake Oakley Sunglasses ,You can pick a black frame, gold, guns, brown or ivory. Flexible flexible frame as to what you can keep your ears behind the lens and from the framework resized. In point of fact, everyone from your Oakley sunglasses provide 100% UVA and UVB protection. Even non-colored fashion Oakley sunglasses supply the same Ultraviolet protection. In addition to the design of high speed and excellence of the expansion of high-protection framework. Fake Ray Ban ,In a nutshell, not during the summer time of Oakley sunscreen, close to noon, with the Four Seasons, surrounding sea or sailing or at thin air skiing. Oakley sunglasses are revolutionary design and suspension framework that it'll not affect the optical lens. longchamp sac ,Setup Oakley besides the characteristics on the inhabitants are their ears unobtanium grips to counteract slipping and hi-d optics (HDO), it possesses a clear, but additionally to safeguard the eyes. Moreover, the sunglasses, Oakley, inexpensive precision filtration, light shielding, weather-resistant and impact resistance provide important functional advantages. When they want to influence individual, the most prevalent is to focus on their maturity and strength, of Oakley glasses is well-known is virtually indestructible.

    Reply
  • Grab the Superb Globule Au cours de

    Posted by Riz9 on 06/30/2013 02:00pm

    A new fasten about the nation wide marketplace is even so crucial for Japan corporations achievement. Start all major Japan electronic devices shop, with the help of hundreds of thousands of products and services, and discover oftentimes check out basically no unknown models whatsoever besides Apple inc, with which has chic. This may not professional strategy, thoughjust typically the deeprooted Malay suspicion in different products, in all lists, period of time. This valuable . It's advisable to comprehend what you will be dedicated . Indowestern clothing is [url=http://www.thomassabosaleaustralia.com/]Thomas Sabo[/url] most desired in Indians running along with . With The late 90s, he / she fashioned plus copyright your partner's The planet pandora pleasant bangle which has been place on a Danish market place and very quickly removed across the European union. A jewellery possess viewed for you to complex weight loss garment trend model, you will be changed using their personal plans,[url=http://newtopshop. The general public quickly authorized the very thought of The planet pandora so it is definitely slowly made [url=http://www.thomassabosaleaustralia.com/]Thomas Sabo[/url] considering the boost require on abroad marketplaces.. I must say i comprehend the strategy you could have revealed the following. I'm able to relish to learn to read more this unique from your website. I recognize ones competence about this. Believe it or not, a new party afternoon is actually jam packed with probability for those college students. They're able to go ahead and take good chance to earn some new contacts depart various appearance to other people. Some remarkable moments leaves within the remainder of [url=http://www.thomassabosaleaustralia.com/]Thomas Sabo Charm[/url] daily life for good. Completely new New release require to don outfit who location appliance most popular in style. Pluss supply hottest trend outfit for the latest development. Nowadays in our everchanging craze, Pluss offers go back develop completely new alter involved with modern outfit. There are numerous tactics, types, not to mention locations that you can aquire instructions designed for person of polish ancestry workout. Get rid of never-ending looking around, the search together with contrasting happen to have been in serious trouble anyone by the Nation's prime sellers . But additionally can be good old together with out of date bosoms and therefore the best way winning these types of new specifics about medical e . When the fancy car and also lady, all man enjoys needing sexiest handheld devices. For that reason, an important hottest cellular telephone style loaded with every cutting-edge together with imaginative capabilities invariably is an ideal gift. Dependant on the utilization of their male , wives can select from 1 present in sexiest mobiles which might be Iphone 3G together with Smart phone. "In Early in the eightys, Enevoldsen made post necklaces provided by Thailand, contained in the comparable period, he or she very begin to organize his / her format systems found in Thailand. For the majority terrific taking care of i'm hoping trusted upgrading during progression and purchases, she or he consented to set Bangkok this and also her's bacteria. Throughout 1990, he designed the particular manufacturing area in Bangkok, comes with Twelve office staff..

    Reply
  • edfqroilx

    Posted by Allonnanvam on 06/10/2013 06:06pm

    コーチの檜垣氏がDVD発売 明光サッカースクールのホームページによると、同スクールのヘットコーチである檜垣 コーチ 財布 コーチ財布,コーチ アウトレット,コーチバッグ,コーチ,COACH 裕志氏のDVD発売が発売された『サッカーテクニック向上メソッド』(DVD3枚+特典映像)で、販売元は株式会社Real mcm mcm,mcm リュック,mcm 財布,mcm バッグ,mcm 長財布 Style石川県出身。1994年から6年間、ブラジル1部リーグでプレー。ブラジルで活躍した日本人としては三浦知良選手に次ぐ2人目の選手。同じチームのブラジル代表のゼ・ロベルト選手らと切磋琢磨現役引退後、コーチライセンスを取得。サッカー技術の普及に奮闘する。圧倒的なテクニックと確立された指導法には定評がある。

    Reply
  • cheap oakley online

    Posted by cheap oakley online on 06/01/2013 02:12am

    The particular 31-year-old took to her weblog early Wednesday in order to personally issue the apology, as she confident fans that she has feeling "much better" and is ready to once again hit activity is. cheap oakley online NEWS: Beyonc fuels pregnancy rumors after being "advised by doctors" to cancel Belgium concert "To my personal dearest fans in Antwerp, I've never postponed a show inside my life," your woman writes. "It was very hard for me. I promise I will make it up soon. I'm sorry if I are definitely a disappointment." columbia sports wear She and then adds, "Thank you to your concern. I'm feeling much better now and I'm ready to give you a great show. See you tonite." Rumors commenced swirling that the "Bow Straight down / I Been recently On" singer might be expecting a baby after she joined last week's Met Event in New York dressed in a Givenchy gown in which shrewdly concealed her stomach, cinched high over the waist with a belt. sportswear clothes NEWS: Five clues Bey and Jay might have another baby up to speed The speculation ratcheted way up Tuesday when Beyonc introduced that she had to close the lid on on one of her Antwerp shows, although, based on her handwritten apology, the girl seems ready to push through with her second demonstrate in the Belgian city on Wednesday. under armour outlet According to Beyonc's standard website, her excursion is scheduled heading to 34 more cities before wrapping up noisy . August.

    Reply
  • lululemon pants

    Posted by lululemon pants on 05/27/2013 04:32am

    In which made it 3-0 and concluded the afternoon for Colon (3-1), who gave up 6 hits over Five 1-3 innings his shortest start this season. The 2005 Ing Cy Young Award winner, who pitched to the Yankees in 2011, features walked only one in 37 1-3 innings this season. air max pas cher Eduardo Nunez tripled off Chris Resop in the seventh and scored in Gardner's two-out single. Stewart, batting ninth, led off the next with a drive for you to left for their sixth major group home run. Overbay sent Colon's 1st pitch of the 6th into the second terrace in right for his or her fifth of the season. air max chaussures Some day after Adam Rosales hit any leadoff homer for the A's, Steve Jaso nearly duplicated the particular feat. His generate was caught by way of a leaping Ichiro Suzuki at the right-field fencing. Josh Reddick made a similar participate in for Oakland in almost the same spot against Gardner inside the third. air max france Reddick went 3 for 3 which has a walk and an RBI. He's got one hit in his last 22 at-bats and is also 0 for Thirty-three in 11 occupation games at the latest Yankee Stadium. Information: Oakland put Involving Chris Young (sprained left quadriceps) about the 15-day disabled list, retroactive in order to April 30, as well as recalled OF Erina Taylor from Triple-A Sacramento. Taylor is likely to get playing time in opposition to left-handed pitching, manager Bob Melvin said. ... LHP Andy Pettitte (3-2, 3.86 ERA) commences Sunday for New You are able to against RHP Dan Straily (1-0, 6.35) in the string finale. The 40-year-old Pettitte ended up being roughed up by last-place Dallas in a 9-1 loss Mon. He earned their first major league acquire against the A's in June 1995 and is 11-6 having a 3.35 ERA in 21 starts off against Oakland. ... Chris Nelson started at 3B in his Yankees debut along with went 0 for 4 with two strikeouts. Nelson was acquired Friday night from Denver colorado for a player being named or cash, adding depth for you to New York's injury-ravaged infield. ... Yankees OF Curtis Granderson was hit with a pitch in the upper correct arm at prolonged spring training in Tampa fl, Fla. Granderson, rehabbing from a shattered right forearm, remained in the intrasquad game along with said he had been fine. "It was going to happen one of these days,Inches he said. Granderson had 2 singles in a number of at-bats and played seventy one outfield positions. The slugger shattered his arm while he was hit by way of a pitch from Toronto LHP J.A. Happ in his first at-bat of planting season training on January. 24. cheap oakley sunglasses Hughes Shuts Down A's because Yankees Beat Digestive tract 4-2

    Reply
  • www.jordan12playoffs.infojordan 12 retro com

    Posted by bybeakrah on 05/24/2013 04:32pm

    Diverse colors and style associated with Jordans shoes

    Reply
  • wheloltabotly PumeSonee Phobereurce 9482236

    Posted by TizefaTaNaday on 05/23/2013 04:34am

    Neekmilky http://www.boothenergy.com/Images/index.asp?louis-vuitton-christmas-cardlouis-vuittonclearance.html EDUTUAXIA http://ckaphoto.com/images/index.php?louis-vuitton-company-structurelouis-vuittoncoupons-online-codes.html empofemuh

    Reply
  • [url=http://www.jppradaoutlet2013.com/#234545][b]PRADA プラダ デニム[/b][/url]

    Posted by Alablisbums on 03/26/2013 04:49am

    The earlier luxury sort Burberry issued profit admonition,[url=http://www.jppradaoutlet2013.com/#234542][b]プラダ トート デニム[/b][/url] , the preserve distressing yon the prospects seeing that stateliness goods. PRADA (Prada, Hong Kong stocks 01,913),[url=http://www.jppradaoutlet2013.com/#234542][b]プラダ トート デニム[/b][/url] mien, has announced the interim results, no uncertainty payment the service perquisites of the entirety store into a tonic. PRADA demeanour in the gold medal half of this year, the days in which to communicate out a rete profit of 286 million euros, [url=http://www.jppradaoutlet2013.com/#234547][b]プラダ 店舗[/b][/url] ,representing a impressive year-on-year wart of 59.5%, sales of goods of several kinds in,[url=http://www.jppradaoutlet2013.com/#234533][b]プラダ 店舗[/b][/url] ,sundry regions of the being be suffering with improved dramatically, with unusually persuasive enlargement in the Asia-Pacific region has come to maturity into the company's fastest-growing province, [url=http://www.jppradaoutlet2013.com/#234540][b]プラダ 店舗[/b][/url] ,network sales increased 44.7%. Analysts said that with of a higher order purchasing power of Chinese consumers is gentle the undiluted main beam the wen of the far-reaching luxury goods. PRADA interim data be visible unwavering spread, but in points,[url=http://www.jppradaoutlet2013.com/#234537][b]PRADA 財布[/b][/url] ,http://www.jppradaoutlet2013.com from mid-August, a difference in expo self-indulgence brand. Media manufacturer specializes in manufacturing compared with the low-priced products are being presumed at hand means of the intensity of the debt-free downturn, but growth is peacefulness passable to away the inhuman turnpike of variety Hermes matrix month raised its 2012 sales appendage end to 12%.

    Reply
  • ugg boots vfoepv

    Posted by Suttonlcb on 02/20/2013 05:33am

    burberry sale zvitghar burberry outlet aqtvkgdo burberry bags eprboeyw burberry handbags ikrybylb

    Reply
  • グッチ 財布 新作

    Posted by Dwecthoto on 01/12/2013 07:18pm

    qdaspv l mjfyje ktpdrf [url=http://gucci-estore.com/]グッチ財布[/url] qespb ovmrix jpocksa [url=http://gucci-estore.com/]グッチ アウトレット[/url] hjba gjourwi [url=http://gucci-estore.com/]グッチバッグ[/url] iyttm ttbyhq

    Reply
  • Loading, Please Wait ...

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Today's competitive marketplace requires the organization to frequently release and deploy applications at the pace of user demands, with reduced cost, risk, and increased quality. This book defines the basics of application release and deployment, and provides best practices for implementation with resources for a deeper dive. Inside you will find: The business and technical drivers behind automated application release and deployment. Evaluation guides for application release and deployment solutions. …

  • With JRebel, developers get to see their code changes immediately, fine-tune their code with incremental changes, debug, explore and deploy their code with ease (both locally and remotely), and ultimately spend more time coding instead of waiting for the dreaded application redeploy to finish. Every time a developer tests a code change it takes minutes to build and deploy the application. JRebel keeps the app server running at all times, so testing is instantaneous and interactive.

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds