Search Algorithms

Assume that each of the following expressions indicates the number of operations performed by an algorithm for a problem size of n. Point out the dominant term of each algorithm, and use big-0 notation to classify it.

• a. 2″ — 4n2 + 5n
• b. 3n2 + 6
• c. n3 +n2 —n

For problem size n, algorithms A and B perform n2 and 1/2 n2 + n instructions, respectively. Which algorithm does more work?

Are there particular problem si for which one algorithm performs significantly better than the other?

Are the particular problem sizes for which both algorithms perform approximatel e same amount of work?

At what point does an n4 algorithm begin to perform better than a Ti algorithm?