Algorithm Efficiency Flashcards

Algorithm Efficiency

Efficiency and Big O Notation

$O(n)$ means a loop does $n$ things. Think of it like baking $n$ cookies: more cookies, more time.
Worst-case: The longest possible time, like the worst traffic on your commute.
Average-case: The usual time, like a normal commute.
Best-case: The shortest possible time, like an empty highway.

Algorithm Comparison

One problem, many solutions. Like driving: you can walk, bike, or drive.
- Factorials: Iterative (step-by-step) or recursive (self-calling).
- Sorting: Shellsort, heapsort, quicksort, etc.
Computational Complexity: Finds the best solution.

Significance of Algorithm Efficiency

Efficiency matters with big data. Imagine searching a phone book with 10 names vs. the entire world's phone numbers.

Computational Complexity

Compares algorithm efficiency. Like judging a race by effort and resources used.
Time and space are key, with time being most important.

Computational Complexity Considerations I

Complexity is system-dependent. A fast car (C++) beats a slow bike (Basic).
Compare algorithms on the same "track."

Computational Complexity Considerations II

Don't use real-time. Use logical units: relate data size ( $n$ ) to processing time ( $t$ ).

Time / Size Relationships

Linear Relationship: $t = cn$ . Double the data, double the time. Like buying apples: more apples, more cost.
Logarithmic Relationship: $t = \log_2{n}$ . Doubling $n$ adds one unit to $t$ . Like halving a loaf of bread: each cut takes the same time.

Asymptotic Complexity

Simplify time functions for big data. Ignore small stuff to see the big picture.
This simplification is Asymptotic Complexity.

Asymptotic Complexity Detailed

Complexity theory: Studies resources (time, memory) needed to solve problems.
Time = steps, space = memory.
Other resources: Number of processors.
Differs from computability theory: Can it be solved at all?
A "problem" is a set of questions, each a string. A question is an instance.
Example: FACTORIZE