Algorithm
A step-by-step procedure for performing some task in a finite amount of time.
Data structure
A systematic way of organizing and accessing data.
The running time of an algorithm or data structure operation typically depends on a number of factors. Its running time can be studied by executing it on various test, inputs and recording the actual time spent in each execution. The running time of an algorithm or data structure method increases with the input size.
The running time is also affected by
Hardware environment
- processor
- clock rate
- memory
- disk, etc.
Software environment
- operating system
- programming language
- compiler
- interpreter, etc
The limitations in experimenting running time of an algorithm.
- Limited set of test inputs
- Running times to be performed in the same hardware and software environments.
- Algorithm to be implemented and executed
Experimentation alone is not sufficient, an analytic framework is required to
- take into account of all possible inputs
- evaluate the relative efficiency of any two algorithms
- perform studying a high-level description of the algorithm without implementing & executing.
Components of methodology for algorithm analysis
- a language to describe algorithms
- a computational model
- a metric for measuring running time
- an approach to characterize the running times
Pseudo Code
- mixture of natural language and high-level programming.
- more structured code intended for human reader, not for computer.
- describe the main ideas behind a generic implementation of a data structure or algorithm.
The pseudo-code mixes natural language with standard programming language constructs such as
- Expressions
- Method declaration
- Decision structures
- Condition statements
- Array Indexing
- Method calls
- Method returns