Understanding time complexity of two nested while loop

Question

The following block of code is from a function that finds the minimum number of coins required to achieve a certain amount given by the user. Here two queue "sums" and "costs" are used.

while(Sums.front()<=TargetSum){
    int tempSum = Sums.front(); 
    Sums.pop();
    int tempCost = Costs.front(); 
    Costs.pop();

    for(int i=0;i<TypesOfCoins;i++)
    {
        Sums.push(coins[i]+tempSum);
        Costs.push(tempCost+1);
        if(Sums.back()==TargetSum)
        {
            cout<<"Sums:"; DisplayQueue(Sums);
            cout<<"Cost:"; DisplayQueue(Costs);
            return Costs.back();
        }
    }
}

As far as I know, for nested loops times complexity is the numbers of times innermost loop iterates, so time complexity for this loop should be O(n^2), shouldn't it?

since TypesOfCoins (inner loop range) is a constant (does not depend on any input that is being processed), then the complexity is NOT n^2. And complexity of a code is NOT how many times it iterates. — Khalil Khalaf
– Khalil Khalaf, Commented Jul 14, 2017 at 16:07
@KyleKhalaf Wouldn't it be O(1) complexity? I'm still learning about it, but that's what makes sense to me. — Rivasa
– Rivasa, Commented Jul 14, 2017 at 16:34
@Annabelle or OP, if a loop iterates the same number of times whatever the input data is (means loop range does not depend on input), then the complexity of this loop is O(1) (which is ~= will not be taking into consideration). I will provide you with a straight forward example as an answer as I think I know what you are trying to understand. — Khalil Khalaf
– Khalil Khalaf, Commented Jul 14, 2017 at 16:37

Khalil Khalaf · Accepted Answer · 2017-07-14 16:56:33Z

The two examples below have the same complexity even that n is different. And their complexity, or Big-O, is O(InputData * 1) which is O(InputData):

int n = 10;
FuncA(int InputData)
{
    for(int i = 0; i < n; i++) // n is outer loop. 
    {
        for(int j = 0; j < InputData; j++) 
        {
            // .. do stuff
        }
    }
}

Or

int n = 100000000;
FuncB(int InputData)
{
    for(int i = 0; i < InputData; i++)
    {
        for(int j = 0; j < n; j++) // n is inner loop
        {
            // .. do stuff
        }
    }
}

n is a constant, and that means any loop that depends on n has O(1) complexity.

InputData is not constant, and that means any loop that depends on InputData has O(InputData) complexity.

Total Complexity = Complexity of all loops => O(InputData * 1)

Note that "Time To Finish" for both functions is different (since n is bigger, hardware speed.. etc). But the "Computation Complexity" is the same: No matter which loop is the inner loop nor how big is the constant (n in this case).

Edit:

A nice idea: if you have a problem and you KNOW how to solve it, but it just requires 10 years of time. Would that be complex?

The answer is no, it is not complex. It is simple but just requires time. (n in my example is times to process something, but the process has no complexity, it is just repeated for a constant amount of time).

Collectives™ on Stack Overflow

Understanding time complexity of two nested while loop

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related