Dynamic Approach For LCA

general
,
1

I reading a LCA Tutorial Where it defines P[1,N][1,logN] where P[i][j] is the 2j-th ancestor of i

alt text


Why it is using **logN** and **why 2j ancestor is used** ?
2

Hello mocshare ,

Both the things

  1. why it is using log(N) .
  2. why 2j is used are related to each other.

for the time, consider a matrix P[1.N][1.log(N)] where P[i][j] represents 2j ancestor of i. I am assuming you are familiar with all the terminologies used in the tutorial mentioned above.

As there are only N nodes only so it may happen that a node has its Nth ancestor (for example if the given tree is a skew tree).so, for that node x we have 2j = N. Therefore, j can take log2(N) value in the worst case.

Please read the above tutorial very carefully it has everything mentioned in detail.