Given a tree, where each node holds a unique number, each of these numbers is represented in $O(log\,n)$ bits. Describe an algorithm to calculate the greatest number $K$ there is.

I would like to get help with understanding the following :

"The number of all bits in all messages needs to be $O(K\times n \,log\,n)$ but the size of a message can be up to $O(log\,n)$"

  • 1
    $\begingroup$ I think you should establish the context clearly. Usually complexity analysis of distributed parallel algorithms uses complexity in no. of messages and bits communicated. Your question does not say it. $\endgroup$ – Devendra Bhave May 9 '17 at 14:50
  • $\begingroup$ @DevendraBhave yeah, so how can I clear myself, it seems that the complexity should be O(k n log n) and the bits communicated O(log n) but what is exactly "bits communicated?" $\endgroup$ – Jeremy Shiklov May 9 '17 at 15:28
  • $\begingroup$ @DevendraBhave never mind my last comment, I read and understood the definition, but now the question is, how exactly is this distributed algorithm different than a usual one, I mean doesn't looking for the greatest one just takes O(number of elements) $\endgroup$ – Jeremy Shiklov May 9 '17 at 15:33
  • $\begingroup$ Assuming parallel computing, you have $n$ processors connected in binary tree configuration -- nodes are processors and edges are network links. Input is set up such that each processor gets one number locally. Distributed algorithm that runs at each node is read numbers from children and compare with the their own and compute max. in three of those and forward it to own parent. No. of messages and size of message matters there. It's not clear to me how it matters to comparison based uniprocessor algorithm. $\endgroup$ – Devendra Bhave May 9 '17 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.