Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự LinearSearch là gì và tại sao?

Đáp án: O(n)

Giải thích: Thuật toán tìm kiếm tuần tự LinearSearch duyệt qua toàn bộ mảng để tìm kiếm phần tử cần tìm. Trong trường hợp xấu nhất (khi phần tử không tồn tại trong mảng), thuật toán phải thực hiện n phép so sánh, với n là kích thước của mảng. Vì vậy, độ phức tạp thời gian của thuật toán là O(n), nghĩa là tuyến tính theo kích thước của mảng.