Search code examples
algorithmperformancetime-complexitypseudocode

What is the time complexity of this peudo code?

I don't have a lot of knowledge computing the complexity. Can you help estimate the complexity of the following pseudo-codes?

Algorithm 1:

Input: V1, V2 and V3 and another vector C// Vectors of size n
Output: response..
V_f = f(V1, V2, 3) // function performs simple multiplication and additions on the vector
for i in range(0,n) // loop over element in the vector
     if V_f(i) != C(i) 
              // sort the V1(i), V2(i) and V3(i) and retrieve the middle value
              // if the middle value is in a range of certain values then launch Algorithm 2  
             // Over the result of Algorithm 2 (using if expressions), print the response
// end and return result

Algorithm 2

Input: Sorted

 Values C{1}, C{2} and C{3} and the vector C

Output: Response:

for i in range (o,n) // loop over the elements 
       // According to the values of C and C{i}, perform additions (using if expressions)
// end and return result

The operations inside the loops are just additions or simple tests. Also, Algorithm 2 is executed withing Algorithm1, which means I have a loop inside a loop (right?):

for i in range (n)
// operations
// for j in range (n)
// operations

So does this mean the time complexity of this algorithm is O(n^2)? where n is the size of of the vector?

Also as a general question, if Algorithm 1 and algorithm 2 are executed in parallel, what is the overall complexity? is it the sum or the max of the complexity of each algorithm?

Solution

  • Algorithm1

    1. The algorithm1 will first perform simple multiplication and addition on vectors. Assuming that it loops from start to end on each vector and performs some calculations, the number of iterations made would be 3*N which would be considered O(N)

      V_f = f(V1, V2, 3)          #Time complexity will be O(N)

    2. The next statement in first algorithm will also loop from 0 to N. Assuming that in each case V_f(i) != C(i) , you will have to sort V1[i], V2[i], V3[i] which will take constant O(1) time.

      for i in range(0,n) // loop over element in the vector
    if V_f(i) != C(i)

      In the next statement, You are checking is the middle value of above sorted elements is in a particular range - // if the middle value is in a range of certain values then launch Algorithm 2 , now the time complexity of this depends on how the checking is done and how big the range is. I will assume that you need to check in a continous range from a to b and so this step will take O(1) only. Now Algorithm2 will be called.

    Algorithm2

    1. Algorithm 2 -

       for i in range (o,n) // loop over the elements 
        // According to the values of C and C{i}, perform additions (using if expressions)
 // end and return result

      Here, you will again be looping from 0 to N and performing some calculation in each iteration which will take O(1). So total time complexity would be O(N) for the whole algorithm2.

    So does this mean the time complexity of this algorithm is O(n^2)?

    Now, assuming the worst-case , you will have to run algorithm 2 in every iteration inside the algorthm1's loop. So, the time complexity would be O(N^2) as you said. Note that this will also depend on how simple the calculations are, how the checking in a range of certain values is done and would contribute to the constant in our final time complexity. But assuming, they aren't more than O(N), your overall time complexity would be O(N^2)