Question abour BFS when using sorted index sequence

kaist-cp / cs500

Moved to https://cp-git.kaist.ac.kr/jeehoon.kang/cs500

25 stars 7 forks source link

Question abour BFS when using sorted index sequence #40

Closed qkrclrl701 closed 5 years ago

qkrclrl701 commented 5 years ago

20190413_213808

The above figure is from the previous answer.

I wonder why N_G(F) costs O(|N_G(F)|log|F|) work and O(log^2|F|) span.

I think, since merge A B has O(|A|+||B|) work and O(log(|A|+|B|)) span, N_G(F) costs differently. (I'm not sure, bit maybe O(|N_G(F)|×|F|) work and O(log(|N_G(F)|×log|F|) span.

Plus, do we need to study about the work efficient merge algorithm that has O(logN) span?

jeehoonkang commented 5 years ago

Please leave your question as a reply to the original thread. (Closing this issue.)
I'll revisit this topic after the midterm exam. You can be sure that the cost analysis of BFS will not be asked in the exam.
I cannot precisely answer questions on the coverage of the exam. Sorry.