Determining Big O(n*n) is relatively straight forward when compared to other forms. Given,
start = 0; end = n; for (i = start; i < end; i++) for (j = start; j < end; j++) doSomething();
It’s clear, for every iteration of the outer loop, the inner loop iterates n times. The outer loop iterates n times as well, so, total number of iterations are n*n. In Big O notation, the runtime complexity may be represented as O(n*n).
But, what about –
start = 0; end = n; for (i = start; i < end; i++) for (j = i; j < end; j++) doSomething();
Note: The inner loop starts iteration at i
The code above represents a very practical use case, for example, when finding indexOf, substring et al.
When determining the runtime complexity, intuition will suggest O(n*n), which, is correct. But, how do we arrive at that? Because at each iteration, i, of the outer loop, we are iterating n-i times in the inner loop. The number of inner loop iterations are decreasing with each iteration of the outer loop.
Let’s break it down by each iteration –
i = 0, inner loop iterations = n i = 1, inner loop iterations = n - 1 i = 2, inner loop iterations = n - 2 i = 3, inner loop iterations = n - 3 ... i = n - 2, inner loop iterations = n = (n - 2) = 2 i = n - 1, inner loop iterations = n - (n - 1) = 1
Sum total of all iterations –
n + (n - 1) + (n - 2) + (n - 3) .... 2, 1
If we reversed the above, it will look like an arithmetic series of positive integers up to n.
1, 2 ... (n - 3) + (n - 2) + (n - 1) + n
Which, as we know is equivalent to –
The above expands to –
(n*n)/2 + (n/2)
In Big O notation (a notation of asymptotic analysis), we drop the lower terms, which, leaves us with –