2

We were given the problem for which I came up with a solution. Could somebody help me identify the time complexity for the given solution? Should it be O(n) or O(n^2)? According to me it should be O(n).

Problem

Write a program to print the sum of the elements of an array following the given below condition.

If the array has 6 and 7 in succeeding orders, ignore the numbers between 6 and 7 and consider the other numbers for calculation of sum.

Eg1) Array Elements - 10,3,6,1,2,7,9 O/P: 22 [i.e 10+3+9]

Eg2) Array Elements - 7,1,2,3,6 O/P:19

Eg3) Array Elements - 1,6,4,7,9 O/P:10

Solution

outer: for (i = 0; i < elementsCount; ++i) { if (arr[i] == 6) { int sumBetweenBounds = arr[i]; for (j = i + 1; j < elementsCount; ++j) { if (arr[j] == 7) { i = j; continue outer; } sumBetweenBounds += arr[j]; } sum += sumBetweenBounds; continue; } sum += arr[i]; }
Improve this question
3
  • 1
    You're right. It's O(n). Commented Nov 5, 2020 at 17:23
  • Thanks for the confirmation @OmG. Commented Nov 5, 2020 at 17:26
  • 1
    You're not right, it's O(n^2). Sorry. Commented Nov 5, 2020 at 17:28

3 Answers 3

Reset to default
7

When talking about time complexity, we should differentiate between best-case, worst-case or average-case scenario (https://en.wikipedia.org/wiki/Best,_worst_and_average_case). When it is not mentioned, worst-case scenario is usually intended.

In the worst-case scenario, your algorithm is O(n^2) because of the inner loop running when the array element is 6. In the worst-case, all array elements could be this value.

In the best-case scenario, it is O(n), but this is usually not interesting.

For average-case analysis, you would need to know the distribution of values in all arrays that your algorithm will be run on.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

If the elements are randomly chosen from a distribution where 7 has a positive probability, the average case will be O(n). So it is safe to say that, except in pathological cases, it is a O(n) algorithm.
@btilly but we care about those pathological cases. Usually when solving such problems all that matter is the worst case analysis.
@btilly: Where is the distribution mentioned in the question? Why is this a correct assumption? And even if it is so, you would only be talking about average-case time complexity; like I said above, in complexity analysis, the worst-case scenario is used when the required scenario is not specified.
@Raz If that was true, nobody would uses hashes. We's also be less happy than we are with the Simplex method.
The question didn't mention the distribution. I was adding to your point that we would need to know the distribution of values in all arrays that the algorithm would run on.
|
2

First, your algorithm wont work for an array of only 6's.

Second, Your algorithm complexity is O(n^2), check the case of an array of only 6's.

If there are only 6's you'll keep getting into the inner loop for every element which will give you the mentioned complexity and also keep summing up 6's that you already summed up before.

For example:

int[] arr = new int[]{6,6,6,6};

will give:

//1st iteration sum += 6+6+6+6; //2nd iteration sum += 6+6+6; //3rd sum += 6+6; //4th sum += 6;

Which in total gives sum=60 instead of 24.

Improve this answer

1 Comment

That's a valid point. Seems like I need to refine it a bit. Thanks.
0

You make solution more complicated that actually problem, you should have use single for loop and you could have used boolean to check weather you want to add element or not

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.