Complex Networks

32 

Complex Networks: An Algorithmic Perspective

to recurrences as in Eqn. (3.1), but when the initial condition T(0) = 0 is considered,

we will find one solution. We can use a method called backward substitution to solve

Eqn. (3.1) where values of n are replaced by its previous values as follows:

T(n) = T (n −1) + 1 (3.2)

= [T (n −2) + 1] + 1 = T(n −2) + 2

= [T (n −3) + 1] + 2 = T(n −3) + 3

As can be seen, there is an emerging pattern. We would still need mathematical

proofs that this pattern is valid for any n. Substituting the initial condition in this

pattern yields:

T(n) = T(n −1) + 1 = T(n −i) + i (3.3)

= T (n −n) + n = T(0) + n = n

This may have been ...