0
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – Raphael♦ Apr 27 '17 at 18:12
  • $\begingroup$ 1) You need to use Landau symbols. 2) See our reference questions. 3) See also algorithm-analysis+loops. $\endgroup$ – Raphael♦ Apr 27 '17 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.