Reference no: EM13833050

1. What is the big-O run-time of the following C++ function. It can be assumed that rand() runs in constant time (Show your work):

template <typename T>

void Foo (T a r r [ ] , int n)

{

for ( int i = n - 1 ; i > 0 ; --i )

{

int j = rand ( ) % i ;

T tmp = a r r [ j ] ;

a r r [ j ] = a r r [ i ] ;

a r r [ i ] = tmp ;

}
}

2. What is the big-O run-time of the following C++ function (Show your work):

template <typename T>

void Baz (T ar r , int n)

{

for ( int i = 0 ; i < n ; ++i )

{

for ( int j = i + 1 ; j < n ; ++j )

a r r [ i ] [ j ] = 0 ;

}

}