CODEWITHSUNDEEP
javascriptalgorithmcachingbig-opalindrome
Newbie
Newbie

Reputation: 23

Big O analysis of solving longest palindromic subsequence by recursion with cache

I am not good at algorithm analysis. The source code is from this place: https://repl.it/KREy/4

Instead of dynamic programming, this piece of code uses a cache to optimize the BigO by sacrificing memory. However, I just don't know how to calculate the BigO mathematically after this cache mechanism is added. May anyone genius give an explanation?

To ease reading I will copy and paste them in the following space: 

// using cache to optimize the solution 1 from http://www.techiedelight.com/longest-palindromic-subsequence-using-dynamic-programming/


const cache = {};

var runningtime = 0;
var runningtimeWithCache = 0;


function computeGetLP(x, start, end){

  const answer = a => {
    runningtime++;
    return a;
  }

  console.log("try to compute: " + x + " " + start + " " + end + " ");


  if(start > end)
    return answer(0);

  if(start == end)
    return answer(1);

  if(x[start] == x[end])
    return answer(2 + computeGetLP(x, start+1, end-1));

  return answer(Math.max(computeGetLP(x, start+1, end),
                  computeGetLP(x, start, end-1)));
}

function computeGetLPWithCache(x, start, end){

  const answer = a => {
    runningtimeWithCache ++;
    console.log("do cache: " + x + " " + start + " " + end + " is " + a);
    cache["" + x + start + end] = a;
    return a;
  }

  console.log("try to compute: " + x + " " + start + " " + end + " ");

  if(cache["" + x + start + end]){
    console.log("hit cache " + x + " " + start + " " + end + " "+ ": ",cache["" + x + start + end]);
    return cache["" + x + start + end];    
  }

  if(start > end)
    return answer(0);

  if(start == end)
    return answer(1);

  if(x[start] == x[end])
    return answer(2 + computeGetLPWithCache(x, start+1, end-1));

  return answer(Math.max(computeGetLPWithCache(x, start+1, end),
                  computeGetLPWithCache(x, start, end-1)));
}

const findLongestPadlindrom1 = s => computeGetLPWithCache(s, 0, s.length-1)
const findLongestPadlindrom2 = s => computeGetLP(s, 0, s.length-1)

const log = (function(){
  var lg = [];
  var output = function(text){
    lg.push(text);
  }
  output.getRecord = function(){
    return lg;
  }
  return output;
})();

log("Now let's do it with cache")
log("result: "+findLongestPadlindrom1("ABBDCACB"))
log("running time is: " + runningtimeWithCache)

log("Now let's do it without cache")
log("result: "+findLongestPadlindrom2("ABBDCACB"))
log("running time is: " + runningtime)

log.getRecord();

Upvotes: 1

Views: 340

Answers (1)

Fred Qian
Fred Qian

Reputation: 1111

I'm not an expert in algorithms either, but I remember cache techniques like this from Introduction to Algorithms, chapter 15, just beside Dynamic Programming. It has the same big O to DP, which is O(n^2) in your case.

Each call to computeGetLPWithCache() costs O(1) for it does not contain loops. Consider the worst case where x[start] != x[end] in each recursion. How many times are we going to call computeGetLPWithCache()?

Let n = length(x), [start, end] represent a call to computeGetLPWithCache(x, start, end), and F(n) equals the number of calls. In computeGetLPWithCache(x, 0, n), 2 sub calls - [0, n-1] and [1, n] - are issued. The former costs F(n), and when we're doing the latter, we discover that in each iteration, the first call's [start, end] range is a true subset of [0, n-1] whose result is already written to cache during the [0, n-1] call, thus no need for recursing. Only the second call which has the element n in it has to be calculated; there're n such calls [1,n][2,n][3,n]...[n,n] (one in each stack layer), so F(n+1) = F(n) + O(n).

F(n) = F(n-1) + O(n-1) = F(n-2) + O(n-2) + O(n-1) = ... = O(1+2+...+(n-1)) = O(n^2).

Hope I've got the meaning through. Replies are welcome.

Upvotes: 1

Related Questions