CS 210: DATA STRUCTURES AND ALGORITHMS

Tutorial 2

1. The List ADT is to be extended with a Boolean member function, isOrdered, which determines whether the data items in the list are in ascending order.
1. Write the function definition.
2. Describe the function in terms of Big-O.
   
   
2. The specifications of the insert method in the List ADT (static array implementation) have been changed. Rather than inserting a new element at a specific position, the new element will be inserted in a position determined by the insert function such that the elements of the list are arranged in ascending order after the insertion.
1. Rewrite the method insert (ElemenType item).
2. Describe the running time of the new insert in terms of Big-O.
   
   
3. Algorithm1 does a particular task in "time" of N³, where N is the number of elements processed. Algorithm2 does the same task in a "time" of 3N + 1000.
1. What are the Big-O requirements of each algorithm?
2. Which algorithm is more efficient by Big-O standards?
3. Under what conditions, if any, will the "less efficient" algorithm execute more quickly than the "more efficient" algorithm?