CODEWITHSUNDEEP
c++time-complexity
user7922379
user7922379

Reputation:

What is the time complexity of the following code snippet?

I have written the following code snippet to find the range summaries, i.e., when given a sorted integer array without any duplicates, it returns the summaries as:

/* IP: [0,1,2,4,5,7]
 * OP: ["0->2","4->5","7"]
 */

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> res;

        if(nums.empty())
            return res;

        for(int i=0; i<nums.size(); i++) {
            int lowerRange=nums[i];

            while(((i+1)<nums.size()) && (nums[i+1]-nums[i]==1))
                i++;

            int higherRange=nums[i];

            if(lowerRange!=higherRange) {
                string str=to_string(lowerRange)+"->"+to_string(higherRange);
                res.push_back(str);
            } else
                res.push_back(to_string(lowerRange));
        }

        return res;
    }
};

I am wondering about the time complexity of the above code snippet. In my opinion, I am doing some "task" (execution of the inner while loop) for each element in the array (using the outer for loop). Due to this, in the worst case, the complexity should be O(n^2) in my opinion. On the other hand, I am doubtful because I do i++ in the inner while loop, due to which, I won't do the "task" on all the elements using the outer for loop. Due to this increment, I am visiting all the elements only once in my entire code. So, this should make the complexity O(n). Could someone please confirm if the complexity is O(n^2) or O(n)?

Upvotes: 4

Views: 2359

Answers (2)

Barmar
Barmar

Reputation: 781004

Since the inner loop advances the same iteration variable as the outer loop, any elements accessed by the inner loop are skipped by the outer loop. Together they just access each element once. So that makes it O(n).

In terms of time-complexity, it's like a loop with an if statement in it:

for (i = 0; i < nums.size(); i++) {
    if ((i+1)<nums.size()) && (nums[i+1]-nums[i]==1)) {
        //
    } else {
        //
    }
}

Writing it this way would require different logic to determine when to update lowerRange and higherRange.

Upvotes: 2

user2033412
user2033412

Reputation: 2109

You're advancing in your inner loop, hence it runs in O(n) time complexity.

Upvotes: 0

Related Questions