Big - O Analysis

What is Big-O?

A measure of how an algorithm’s running time grows as the input size (n) becomes very large.

When looking at an expression, which term is typically considered when writing the notation of Big-O (hint: what gets written into the parentheses)?

The highest-degree term.

Describe the scenarios and methodology (if applicable) for O(1) runtime.

• Running time stays the same no matter the size of n, quick in efficiency.

• Common in programs that don’t use loops.

• Data structure operations (insertion, removal, lookup) that occur at the ends of the structure.

Describe the scenarios and methodology (if applicable) for O(n) runtime.

• Linear growth; running time grows proportionally to input size (n).

• Typical in programs that use loops and/or have data structure operations (insertion, removal) within the middle of the structure, regardless of size.

• Traversing a data structure since we could be scanning every element at worst-case scenario.

Describe the scenarios and methodology (if applicable) for O(n²) runtime.

• Occurs in programs that use nested loops (typically when you need to traverse a 2D array).

• Need to traverse a single array n times.

• Insertion sort: inserting an element at the middle of a Data Structure n times.

Describe the scenarios and methodology (if applicable) for O(log n) runtime.

• Occurs in binary search algorithms on data structures (ie. Arrays, Trees) and in general.

• Push and Pop methods on Heaps.

Describe the scenarios and methodology (if applicable) for O(n log n) runtime.

• Found in many sorting algorithms & built-in sorting functions.

Describe the scenarios and methodology (if applicable) for O(2ⁿ) runtime.

• Common in recursive programs.

Describe the scenarios and methodology (if applicable) for O[ sqrt(n) ] runtime.

• Rare, but found in programs that involve finding factors of number(s).

Describe the scenarios and methodology (if applicable) for O(n!) runtime.

• Found in permutation programs and graph problems.

• Most inefficient.

What is the time complexity for sequential for loops (not nested)?

O(n)