CSEN102 Introduction to Computer Science: Lecture 8: Attributes of Algorithms and Measuring Efficiency

This lecture for CSEN102: Introduction to Computer Science, given by Milad Ghantous, PhD, delves into the attributes that define good algorithms and methods for measuring their efficiency.


8.1 Desirable Attributes of Algorithms

Beyond simply providing a correct solution, an effective algorithm should possess several key attributes:


8.2 Measuring Algorithm Efficiency

Measuring an algorithm's efficiency typically involves assessing how its performance (time taken or space used) scales with the size of the input. This is often done using "Big O" notation.

1. Time Complexity:

Refers to the amount of time an algorithm takes to complete as a function of the length of its input. It's not about actual time (which varies by hardware) but about the number of elementary operations performed.

2. Space Complexity:

Refers to the amount of memory space an algorithm needs to run to completion as a function of the length of its input. This includes both the input data storage and any auxiliary space used by the algorithm.


8.3 Asymptotic Analysis and Big O Notation (O-notation)

Asymptotic analysis describes the limiting behavior of an algorithm as the input size grows very large. Big O notation is a mathematical notation that describes the upper bound of an algorithm's running time or space requirements.

Common Time Complexities (from fastest to slowest):

Why Big O Notation?


8.4 Practical Considerations for Efficiency

While theoretical efficiency (Big O) is important, practical considerations also play a role:

Thank you