Suppose I have a task to write an algorithm that runs through an array of strings and checks if each value in the array contains s
character. The algorithm will have two nested loops, here is the pseudo code:
for (let i=0; i < a.length; i++)
for (let j=0; j < a[i].length; j++)
if (a[i][j] === 'c')
do something
Now, the task is to identify the runtime complexity of the algorithm. Here is my reasoning:
let the number of elements in the array be n
, while the maximum length of string values m
. So the general formula for complexity is
n x m
Now the possible cases.
If the maximum length of string values is equal to the number of elements, I get the complexity:
n^2
If the maximum length of elements is less than the number of elements by some number a
, the complexity is
n x (n - a) = n^2 - na
If the maximum length of elements is more than the number of elements by some number a
, the complexity is
n x (n - a) = n^2 + na
Since we discard lower growth functions, it seems that the complexity of the algorithm is n^2
. Is my reasoning correct?