Big O in plain language flashcards

What is Big O notation?

A mathematical representation that describes the efficiency of an algorithm in terms of time or space.

O(1)

Constant time complexity; execution time remains the same regardless of input size.

O(n)

Linear time complexity; execution time increases linearly with input size.

O(n^2)

Quadratic time complexity; performance is proportional to the square of the input size.

True or false: O(n log n) is better than O(n^2).

True, because O(n log n) grows slower than O(n^2) with increasing n.

Difference between O(n) and O(n^2)

O(n) grows linearly, while O(n^2) grows quadratically, making O(n^2) slower.

O(log n)

Logarithmic time complexity; execution time grows logarithmically with input size.

What does upper bound mean?

The worst-case scenario performance of an algorithm, described using Big O.

Fill the blank: O(2^n) is called _____ time complexity.

Exponential time complexity.

True or false: O(n) and O(2n) are the same.

False, because O(2n) is still linear but usually considered O(n).

Which is NOT a valid Big O notation?

O(n!), as it's factorial time complexity and grows very fast.

What is space complexity?

A measure of the amount of working storage an algorithm needs.

When is Big O used?

To analyze and compare the efficiency of algorithms.

What is O(n^3)?

Cubic time complexity; execution time increases with the cube of input size.

Fill the blank: The best complexity you can achieve is _____

O(1), which is constant time.