AA2025-Lecture2-eng.pdf

Algorithms and Data Structures School year 2024-2025 Lecture 2 – Analysis of Algorithms Summary Criteria of analysis Determination of T(n) Complexity of an algorithm Classification of algorithms Case of non-deterministic algorithms Classes of problems...

Algorithms and Data Structures School year 2024-2025 Lecture 2 – Analysis of Algorithms Summary Criteria of analysis Determination of T(n) Complexity of an algorithm Classification of algorithms Case of non-deterministic algorithms Classes of problems 2 Criteria of analysis 1. Execution time/Running time (efficiency) 2. Memory to use Contradictory: it is not possible to simultaneously minimize both criteria The criterion of efficiency is decisive Execution time depends (for a given machine) mainly on the dimension of the input 3 Criteria of analysis Example: Sorting time for a set of items depends on the number of items to be sorted, that is, the input dimension (input size). Given: n= input dimension T = T(n) T= execution time The execution time, while measured in units of time (ex: seconds) varies from machine to machine, for the same algorithm. Then: T(n) = Number of instructions that are executed (or an approximation) 4 Criteria of analysis Measurement of the efficiency of an algorithm independent of the machine on which it runs. “Executed instruction” differs from “algorithm step” Example: 1. A  2 2. DO FOR I=1 TO 10 3. AA*A 4. PRINT (A) 4 steps / 23 executed instructions 5 Criteria of analysis Example: Algorithm Average calculation for a set of n values 1. SUM  0 2. I1 3. DO WHILE I