Analysis tools

Question 1

List all the seven functions in ascending order

Answer 1

1. Constant
2. log n
   3, Linear
3. n log n
4. quadratic
5. cubic
6. exponentia;

Question 2

What is a data structure? What is an Algorithm? And how do they affect runtime

Answer 2

A data structure is a systematic way of organizing and reaching data.

An algorithm is a set of instructions specifying how a specific task must be done within a finite amount of time

They affect runtime deciding how quickly accessible the data in the data structure is, which in turn affects runtime

Question 3

How would you perform experimental studies on an algorithm?

Answer 3

Run the algorithm on a machine, test the algorithm with various input, measure the time the algorithm takes to run by using system.currenttimemillis() and record the results

Question 4

What are the limitations of Experimental studies?(3)

Answer 4

1. It is sometimes impractical to test all possible input
2. The results will not be the same across different machines unless the hardware, software and other contributing factors are exactly the same
3. You have run the whole algorithm in order to analyze it and who knows how long that will take

Question 5

Why is runtime analysis better?(3)

Answer 5

• It takes into account all inputs
• Will analyze the algorithm without implementing it
• Will analyze the algorithm the same regardless of hardware and software