CODEWITHSUNDEEP
algorithmtime-complexity
icantcode
icantcode

Reputation: 167

Complexity in case of 2 while loops nested inside 1 while loop

Here is my code. I want to know how to calculate the time complexity of this very specific part of code. As per the rule, we need to calculate first inner 2 while loops and then add them and then multiply them with outer loop, but i am unable to figure out how to calculate them and then arrive to the answer.

 int start=first,end=last;
int mid= (first+last)/2;
int temp;
while(start<=end)
{
    while(a[start]<a[mid])
    {
        start=start+1;
    }
    while(a[end]>a[mid])
    {
        end=end-1;
    }
    if(start<=end)
    {
        temp=a[start];
        a[start]=a[end];
        a[end]=temp;
        start++;
        end--;
    }
}

Upvotes: 0

Views: 500

Answers (1)

IVlad
IVlad

Reputation: 43487

This is O(end - start).

As per the rule, we need to calculate first inner 2 while loops and then add them and then multiply them with outer loop

There is no such rule. You need to take into account the total number of operations executed. Sometimes you do what you describe, but there is no such general rule.

Think about how often each element is accessed: O(1) times. The inner loops move start and end towards each other. The outer loop does not reset the inner loops, they continue where they left off the previous iteration. Since you do O(1) operations O(end - start) times, this is O(end - start).

Upvotes: 1

Related Questions