Efficiency

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Analysis of Algorithms #◇Data Structures #◇Time Complexity #◇Space Complexity

---

◇Overview

Efficiency measures how well an algorithm uses computational resources (time and space) relative to the input size.

◇Key Concepts

Time efficiency vs. space efficiency Time-space tradeoff Measured using ◇Asymptotic Notation One of the key ◇Algorithm design issues alongside ◇Correctness

◇Details / Theory

Definition

An algorithm is efficient if it uses computational resources (time and memory) wisely as input size grows. Efficiency is one of the primary design goals alongside ◇Correctness.

Two Dimensions of Efficiency

1. Time Efficiency (◇Time Complexity): How many operations the algorithm performs.
2. Space Efficiency (◇Space Complexity): How much memory the algorithm requires.

Time-Space Tradeoff

Often, improving time efficiency requires using more space, and vice versa:
Hash tables use $O(n)$ extra space to achieve $O(1)$ average-time lookups. Memoization caches results to avoid recomputation (more space, less time). In-place algorithms (like Insertion Sort) use $O(1)$ extra space but may be slower.

Measuring Efficiency

Efficiency is quantified using ◇Asymptotic Notation (Big-O, Ω, Θ). We analyze the ◇Order of Growth of $T(n)$ and $S(n)$. An algorithm is considered efficient if it runs in polynomial time ($O(n^k)$ for some constant $k$).

Comparing Algorithms

When choosing between algorithms for the same problem:

1. Compare their asymptotic time complexity.
2. If time complexity is the same, compare space complexity.
3. Consider constant factors for practical (small input) cases.

◇Common Pitfalls

Optimizing for time without considering space constraints (or vice versa). Assuming asymptotic efficiency always translates to practical speed — constants matter for small inputs. Over-optimizing code that isn’t a bottleneck (premature optimization).

◇Summary

TL;DR — Efficiency measures how well an algorithm uses time and space relative to input size. There is often a tradeoff between the two, and efficiency is expressed using asymptotic notation.

◇Links

Related: ◇Algorithm — ◇Correctness — ◇Time Complexity — ◇Space Complexity — ◇Asymptotic Notation — ◇Order of Growth Source / Reference: Handout 01, Page 2

◇References & Navigation

• Previous Topic: ◇Divide and Conquer
• Next Topic: ◇Frequency Count
• Related Notes: ◇Time Complexity, ◇Space Complexity