Đề Cương Ôn Tập KTCK2

Which statement best describes the meaning of the time complexity of an algorithm?

• The actual time the algorithm runs on a specific computer.

• The amount of memory resources the algorithm uses.

• The growth rate of the execution time of the algorithm according to the input size.

• The number of lines of code in the algorithm implementation.

Which operation typically has a time complexity of constant O(1)?

• Iterating through all elements in an array of n elements.

• Searching for an element in a sorted array using binary search.

• Accessing an element at a specific position in an array.

• Sorting an array of n elements using Bubble Sort.

A program segment with a for loop running from 1 to n, performing a finite number of operations with constant time inside the loop. What is the time complexity of this segment?

• O(1)

• O(logn)

• O(n)

• O(n2)

The time complexity of the binary search algorithm in a sorted array is:

• O(1)

• O(logn)

• O(n)

• O(n2)

What is the time complexity of the following code? tong = 0 for i in range(n): for j in range(m): tong += i * j

• O(n)

• O(m)

• O(n×m)

• O(max(n,m))

Given two algorithms A and B solving a problem with input size n. Algorithm A has a time complexity of O(nlogn) and algorithm B has a time complexity of O(n2). Which algorithm will generally run faster for large input sizes?

• Algorithm A

• Algorithm B

• Both algorithms have equivalent running time

• Cannot determine

The Python function len() to get the length of a list with n elements typically has a time complexity of:

• O(1)

• O(logn)

• O(n)

• O(nlogn)

Consider the following code: for i in range(n): k = 1 while k < n: # Some O(1) operations k = k * 2 What is the time complexity of this code?

• O(n)

• O(logn)

• O(nlogn)

• O(n2)

For the following code: for i in range(n): print(i) A student commented: "This code has a time complexity of O(1) because it only has one loop." Which explanation is most appropriate to evaluate this comment?

• The student is correct, as the number of operations inside the loop is constant.

• The student is mistaken, as this loop will execute n times, proportional to the input size.

• The student could be correct if n is a small insignificant number.

• The student should consider the actual running time on the computer to make an accurate conclusion.

Consider the following code: a = 10 b = 20 c = a + b print(c) A student said: "The time complexity of this code depends on the values of a and b." What do you think about this opinion?

• This opinion makes sense, as larger numbers often take more time to process.

• This opinion is inaccurate, as the number of operations here is fixed, regardless of the values of a and b.

• This opinion is only correct if the addition operation is performed using a more complex algorithm.

• This opinion needs to be verified by testing with various values of a and b.