I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms. As a simple example, taking average of n (= 1 billion) numbers can be done on O(n) + C (assuming division to be constant time operation). If i break this massively parallelizable algorithm for Map Reduce, by dividing data over k nodes, my time complexity would simply become O(n/k) + C + C'. Here, C' can be assumed as the startup job planning time overhead. Note that there was no shuffling involved, and reducer's job was nearly trivial. I am interested in a more complete analysis of algorithm with iterative loops over data and involve heavy shuffling and reducer operations. I want to incorporate, if possible, the I/O operations and network transfers of data.
Time Complexity analysis for Map-Reduce model
algorithms;algorithm analysis;runtime analysis;parallel computing