Understanding Asymptotic Notations

What does Big O notation represent?

• Big O notation represents the upper bound of an algorithm's time or space complexity.

• Big O notation is used to compare the efficiency of different programming languages.

• Big O notation measures the average case performance of an algorithm.

• Big O notation indicates the exact runtime of an algorithm.

Binary search is an example of a(n) ________ algorithm.

• Greedy

• Dynamic programming

• Backtracking

• Divide-and-conquer

What does time complexity refer to in algorithms?

• The amount of time required to execute an algorithm

• The number of loops in an algorithm

• The space required to store data in an algorithm

• None

Which of the following shows the correct relationship among some of the more common computing times on algorithms

• . O(log n) < O(n) < O( n* log n) < O(2n ) < O(n²)

• O(log n) < O(n) < O( n* log n) < O(n²) < O(2n )

• O(n) < O(log n) < O( n* log n) < O(n²) < O(2n )  

• O(n) < O(log n) < O( n* log n) < O(2n ) < O(n²)

Lower bound is denoted as _______

• Ω     

• Θ

• ω

• O

What is the time complexity of Merge Sort in the worst case?

• O(n log n)

• O(n)

• O(n^2)

• O(log n)

Which part of the array is typically used as a pivot in the simplest version of Quick Sort?

• First element

• Last element

• Middle element

• Any element, depending on implementation

What is the purpose of asymptotic analysis in computer science?

• To evaluate and compare the efficiency of algorithms in terms of time and space complexity.

• To determine the exact runtime of an algorithm.

• To optimize the user interface of software applications.

• To analyze the hardware requirements of a program.

Strassen's algorithm is an improvement over the standard matrix multiplication algorithm because:

• It reduces the number of matrix additions.

• It reduces the number of scalar multiplications.

• It eliminates the need for recursion.

• It increases the number of multiplications to improve speed.

Tags

CCSS.HSN.VM.C.8

What is the time complexity of Strassen’s Matrix Multiplication algorithm?

• O(n^3)

• O(n^2)

• O(n^2.81)

• O(n log n)