Deep Space Communication channel basically operates in a highly power-limited regime and as a result has a very low signal-to-noise ratio; to a great extent it becomes obvious to decide upon better coding techniques to achieve high coding gain, high spectral efficiency to aim for less probability of error and ultimately reach Shannon limit. Based on this view point, in 1970s Reed-Solomon Convolutional Concatenated (RSCC) codes captured lot of attention with rate-14 inner convolutional code and a variable-strength Reed Solomon outer code which achieved coding gain of nearly 10.2 dB with probability of error approximately 2.10-7. However, in terms of error probability a better coding scheme called Turbo codes a capacity approaching code were developed by Jet Propulsion Laboratory (JPL) that had very low error rates at a moderate block lengths. In this paper, our aim is to analyze decoding complexity of concatenated Reed - Solomon Convolutional codes and Turbo codes by their trellis complexity and their state dimension profile. © 2015 IEEE.