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

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.

Given a string of n elements,

If you start with 1st element, you can form n strings

If you start with 2nd element, you can form n-1 strings .... so on...

For example, take 1234

1,12,123,1234

2,23,234

3,34

4

As you can see, the total is n + (n-1) + (n-2) ...1 i.e. sum of n elements which is n(n+1)/2

Simply a substring is defined by two parameters [i,j] which are start index and end index for substring in the original string . Now 0<=i,j<=n as indices should be within the string, Total values i&j each can have are n so all combinations of [i,j] would be n*(n+1)/2 which is O(n^2)