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
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
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 ;
}
}