Number of substrings in a string: n-squared or exponential

Question

How many subtrings are there in a string in general?

Why does string x [1:n] have O(n^2) subtrings according to the lecture 21 Dynamic Programming III of        
6.006 from MIT? 
Why it is not O(2^n)?

Here is a link [http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec21.pdf]

Answer 1

Take a string length n=4, say: "ABCD"

The sub-strings of the above are (by length):

• 1 character: A,B,C,D (4 sub-strings)
• 2 character: AB,BC,CD, (3 sub-strings)
• 3 character: ABC,BCD (2 sub-strings)
• 4 character: ABCD (1 sub-string)

Totaling the numbers yields: 1+2+3+4 = 10.

So, to generalize, the number of possible sub-strings is the sum of all integers from 1 to n.

This sum is calculated using the formula (n^2 + n) / 2 (see here: Sum of Consecutive Numbers)

So the efficiency is of the n^2 order of magnitude.