Rules for Computing Order Constant multipliers can beignored:F( N ) = 25N=>O( N)

Question

Rules for Computing Order

Constant multipliers can beignored:F( N ) = 25N=>O( N)

Addition of terms is done byselecting the maximum term:O( M + N )=>O( max ( O( M ), O( N ) ))

F( N ) =N2+N=>O( N2)

Multiplication of terms isperformed:O( M ) * O( N )=>O( M * N)

O(N2) * O( N)=>O( N2* N )=O(N3)

ListType temp =first;

first = second;

second = temp;

return;

int partition( ListType list [], constint left, const int right )

ListType pivot;

int lastMin;

pivot = list [ left];

lastMin = left;

for ( int count = left + 1; count <=right; ++count )

if ( list [ count ] < pivot)

++lastMin;

swap( list [ lastMin ], list [ count ]);

swap( list [ left ], list [ lastMin ])

return lastMin;

Explanation / Answer

ListType temp =first;         O(1)

first =second;                     O(1)

second =temp;                 O(1)

int partition( ListType list [], const int left, const int right)

ListTypepivot;               

int lastMin;

pivot = list [ left];             O(1)

lastMin =left;                    O(1)

for ( int count = left + 1; count <= right; ++count)            O(n)

if ( list [ count ] < pivot)                             O(1)

++lastMin;                                                    O(1)

swap( list [ lastMin ], list [ count ]);                    O(c)

swap( list [ left ], list [ lastMin ])                        O(c)

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.