What is the time complexity of the following code snippet?

Question

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)?

I think you're correct. The inner loop advances the index of the outer loop, so it's really like just one loop. — Barmar
– Barmar, Commented Jul 6, 2017 at 21:28
@Ramesh I was a little to fast to comment. Linear is the correct answer :) — iehrlich
– iehrlich, Commented Jul 6, 2017 at 21:29
@Barmar, but then in the worst case, inner while loop (which might access all the elements) will be executed for each element by the outer for loop. So, wouldn't it be O(n^2) then? — user7922379
– user7922379, Commented Jul 6, 2017 at 21:33
Re, "I am doing some 'task' (execution of the inner while loop) for each element in the array." No, because the inner loop and the outer both increment the same variable. Your function only scans the array one time from beginning to end. It could be re-written as a single loop if you added some state variables. — Solomon Slow
– Solomon Slow, Commented Jul 6, 2017 at 21:34
Any elements accessed by the inner loop are skipped by the outer loop. Together they just access all the elements once. — Barmar
– Barmar, Commented Jul 6, 2017 at 21:35

Barmar · Accepted Answer · 2017-07-06 21:43:53Z

2

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.

answered Jul 6, 2017 at 21:43

Barmar

789k57 gold badges555 silver badges669 bronze badges

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

1 Comment

user7922379 Over a year ago

Sorry, I had to accept @T33C's answer since it appears to be more elaborate. I wish I could accept both.

user2033412 · Accepted Answer · 2017-07-06 21:29:05Z

0

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

answered Jul 6, 2017 at 21:29

user2033412

2,1573 gold badges29 silver badges55 bronze badges

Collectives™ on Stack Overflow

What is the time complexity of the following code snippet?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related