# Time Complexity analysis for Map-Reduce model

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.

• There is no way to measure asymptotics. Are you interested in benchmarks or formal analysis? The latter is tough in parallel settings, and depends on your exact machine model. Chances are, if you assume a model that you can handle during analysis, the results won't tell you much in practice. – Raphael May 7 '15 at 7:26
• That said, this question may be relevant. – Raphael May 7 '15 at 7:28
• Have you seen Mining of Massive Datasets? Sections 2.5 and 2.6 talk about minimizing communication (I/O) costs and not compute time which is usually the real bottle neck in Hadoop – Eric Farng May 7 '15 at 13:14
• In the papers I've read you don't really analyse the time complexity. You count the number of rounds and the amount of data you need to process in each round (the communication complexity). Shuffling the data through the network is typically the bottleneck in map-reduce. – adrianN Dec 28 '16 at 9:15

Communication complexity concerns the following scenario. There are two players with unlimited computational power, each of whom holds an $n$ bit input, say $x$ and $y$. Neither knows the other’s input, and they wish to collaboratively compute $f(x, y)$ where the function $f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$ is known to both. Furthermore, they had foreseen this situation (e.g., one of the parties could be a spacecraft and the other could be the base station on earth), so they had already — before they knew their inputs $x, y$ — agreed upon a protocol for communication. The cost of this protocol is the number of bits communicated by the players for the worst-case choice of inputs $x, y$.