What will be time complexity for the given algorithm?

user_6687712 0
Viewed 96

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];
        }
data-structures algorithm java
3 Answers

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.

user_5764370

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.

user_145359290

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

user_91833280
Related