Due to the high computational and power consumption demands of modern embedded visual media processing, MPSoC architectures often contain multiple heterogeneous processing elements, which introduced numerous problems involving the mapping of algorithm functionality and possible refinements of each processing element. To cope with these challenges, algorithm and architecture co-design (AAC) is significant for characterizing the algorithmic complexity used to optimize targeted architecture. This paper proposes the efforts towards a systematic complexity analysis for AAC by timed mode of computing (MoC)-based analysis. Through such seamless approach, complexity measures intrinsic to the algorithm, such as degree of parallelism and pipeline depth, can be fully exploited. Furthermore, the resulting explicit architecture/algorithm friendliness will greatly help the mapping of algorithm to differential processing elements. As an example, an ideal architecture prototype of deblocking filter for H.264 was proposed, which can achieve 144 cycles/macroblock throughput, and also several deblocking filter designs in the literature have been compared and illustrated to demonstrate the benefits of analysis and exploitation of complexity measures with our approach in the early system-level design.