What's the optimal scalability of some algorithm when I implement it in a distributed manner?
Intuitively, it seems to me that any algorithm can scale at most linearly with number of computing nodes. I.e, if algorithm A takes T units of time with 1 computing node on input I, it can't run faster than T/n units of time with n computing nodes on the same input I.
Is my intuition correct or are there some weird counter-examples to it?
Yes, your intuition is correct, for all the reasonable models of computation that I'm familiar with. If it weren't, then we could take a single machine and have it simulate a cluster of n nodes, increasing the cost by only a factor of n. So, if you had an algorithm that ran on a cluster of n nodes faster than T/n, you'd get an algorithm that runs on a single node faster than T.
Note that the single node might need to have n times as much memory as each node in the cluster.
