Modify a data structure : Big O Notation and Calculating the Runtime of a Function

The video introduces Big O notation, a method to classify algorithm scalability and runtime efficiency. It covers different time complexities: constant (O(1)), linear (O(n)), exponential (O(n^2)), and logarithmic (O(log n)), using examples to illustrate each. The video emphasizes the importance of understanding these concepts for efficient programming.

What does Big O notation help us understand about an algorithm?

• The memory usage of the algorithm

• The scalability and performance based on input size

• The number of lines of code in the algorithm

• The exact time it takes to run

If a function logs the first two elements of an array, what is its time complexity?

• O(n^2)

• O(1)

• O(n)

• O(log n)

How does the runtime of a function with linear time complexity change as the input size increases?

• It increases exponentially

• It decreases

• It remains constant

• It increases proportionally

What is the time complexity of a function that generates all possible pairs from an array?

• O(log n)

• O(n^2)

• O(n)

• O(1)

Why is exponential time complexity considered inefficient?

• It requires a lot of code

• It becomes very slow with large inputs

• It is difficult to implement

• It uses too much memory

In a binary search, how is the input size reduced with each operation?

• By one element

• By a constant factor

• By doubling

• By half

What is the time complexity of binary search?

• O(1)

• O(log n)

• O(n^2)

• O(n)