Understanding Time Complexity with Big O Notation

This lesson covers the determination of time complexity using Big O notation through three examples. The first example discusses non-nested loops with a time complexity of O(n + m). The second example involves nested loops, resulting in a time complexity of O(n * m). The third example examines an algorithm with logarithmic complexity, O(log n). A reference table is provided for better understanding.

What is the purpose of the reference table shared at the beginning of the lesson?

• To list all programming languages

• To provide a guide for time complexity descriptions

• To explain the history of algorithms

• To show examples of code syntax

In the first example, what is the time complexity of the algorithm with two non-nested loops?

• O(log n)

• O(n * m)

• O(n^2)

• O(n + m)

Why does the first example have a time complexity of O(n + m)?

• Because it has a single loop

• Because it skips elements

• Because it has two nested loops

• Because it has two non-nested loops

In the second example, what is the time complexity of the algorithm with nested loops?

• O(n + m)

• O(log n)

• O(n * m)

• O(n^2)

What causes the time complexity to be O(n * m) in the second example?

• The algorithm skips elements

• The use of recursion

• The presence of nested loops

• The presence of a single loop

In the third example, what is the time complexity of the algorithm that skips elements?

• O(n^2)

• O(n + m)

• O(log n)

• O(n * m)

Why does the third example have a time complexity of O(log n)?

• Because it has a single loop

• Because it skips elements

• Because it uses recursion

• Because it has nested loops