Question & Answer: 5. Determine the Big-O of this algorithm. Explain your answer…..

We calculate the Big O classificaton of given function as follows;

Algorithm (A,r)

->if(r.isLeaf)

->for i = 0 to r.head

output A[i]

->for j = 0 to r.size( )

if (A [ j ] != NULL )

Algorithm (A , A[ j ] )

Step 1: Identify the Formula

1. We are Comapring r is leaf or not so the compexity is O( N ) beacause it runs n times

2. There are two for Loops in the algorithm so the complexity of both is 2N beacause Big O complexity of one loop is N as it runs n times.

3. Again for the if Statement the Complexity is O( N ) and the recursive function Algorithm ( A, A [ j ] ) called many times as if Statement so the complexity is O ( N )

Now the Total Complexity is : N + 2N + N + N = 5N

Step 2: remove Everything Except the higher terms:

There is Only single term in notation so we can’t eliminate any term.

So the Complexity is Still 5N

Step 3: Remove all the Constants:

Remove the constant 5 and remaining part is final comlexity i.e. N

Big-O for given algorithm is O ( n ) .