CODEWITHSUNDEEP
algorithmbig-o
Duy Hà
Duy Hà

Reputation: 41

Time complexity of a program with multiple algorithm

So I as I know if I my program have something like this -

     method 1:
     for (int i = 0; i < N; i++) 
       statement;

Time complexity of the algorithm will be O(N), or

     method 2:
     for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
       statement;

It will be O(N^2)

What if my program is the combination of several loops like this separately? Like -

method1: statement;
method2: statement;

or

method1: statement;
method1: statement;
method1: statement;

Will that increase the total time complexity of the system? Or just take the highest of them all and go with that?

Upvotes: 1

Views: 526

Answers (1)

Abhishek Bhagate
Abhishek Bhagate

Reputation: 5786

When the loops are nested, the time complexity gets multiplied. For eg-

loop(1 to n1):
    loop(1 to n2):
        loop(1 to n3):
            # Some code here

In the above case , time complexity would be O( n1*n2*n3 ). When the loops are run in parallel, the time complexity gets added. For eg -

loop(1 to n1):
    # Some code here
loop(1 to n2):
    # Some code here
loop(1 to n3):
    # Some code here

In the above case, time complexity would be O( n1 + n2 + n3 ).

What if my program is the combination of several loops like this separately?

1. First Example -

method1: statement;
method2: statement;

In the above code, your method1 has time-complexity of O(N) and method2 has time-complexity of O(N^2). So, we have an overall time-complexity of -

O( N ) + O( N^2 ) = O( N + N^2 ) = O( N^2 )

In the upper-bound time complexity, we generally ignore the lower-order terms and simplify the final time-complexity that we get. So the answer would be O(N^2) in the above example.

2. Second Example -

method1: statement;
method1: statement;
method1: statement;

We can calculate time-complexity in a similar manner. We will have a time complexity of -

O( N ) + O( N ) + O( N ) = O ( 3*N ) = O ( N )

Another rule while calculating upper-bound time-complexity is that we ignore constant terms that we get in our time-complexity.

These rules can easily be extended to similar examples. No matter how many loops are in parallel, we will take the summation of each loop and apply the above two rules and that would be our final time-complexity. Similarly, for nested loops, we will multiply the time-complexity of each loop and that would be our final result.

Hope this helps !

Upvotes: 3

Related Questions