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

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

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

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

Hello mocshare ,

Both the things

- why it is using log(N) .
- why 2
^{j}is used are related to each other.

for the time, consider a matrix P[1.N][1.log(N)] where P[i][j] represents 2^{j} 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 N^{th} ancestor (for example if the given tree is a skew tree).so, for that node x we have 2^{j} = 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.