Common complexity classes (O(1), O(n), O(log n), O(n²)) in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to represent the time complexity of accessing an element in an array.

Data Structures Theory

time_complexity = "O([1])"

Drag options to blanks, or click blank then click option'

A1

Bn

Clog n

Dn²

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing O(n) because they think it depends on the size of the array.

Confusing O(1) with O(log n).

Accessing an element in an array takes constant time, which is O(1).

2fill in blank

medium

Complete the code to represent the time complexity of searching for an element in an unsorted list.

Data Structures Theory

time_complexity = "O([1])"

Drag options to blanks, or click blank then click option'

A1

Bn²

Clog n

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing O(1) because they think search is instant.

Choosing O(log n) which applies to sorted data with binary search.

Searching in an unsorted list requires checking each element, so it takes O(n) time.

3fill in blank

hard

Fix the error in the code to represent the time complexity of binary search on a sorted list.

Data Structures Theory

time_complexity = "O([1])"

Drag options to blanks, or click blank then click option'

Alog n

Bn

C1

Dn²

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing O(n) which is linear search complexity.

Choosing O(1) which is constant time.

Binary search divides the list in half each time, so it runs in O(log n) time.

4fill in blank

hard

Fill both blanks to represent the time complexity of a nested loop iterating over n elements twice.

Data Structures Theory

time_complexity = "O([1][2])"

Drag options to blanks, or click blank then click option'

An

B1

C²

Dlog n

Attempts:

3 left

💡 Hint

Common Mistakes

Using O(n) instead of O(n²).

Using O(log n) which is incorrect for nested loops.

A nested loop over n elements twice results in O(n²) time complexity.

5fill in blank

hard

Fill all three blanks to create a dictionary showing time complexities for access, search, and binary search.

Data Structures Theory

complexities = {"access": "O([1])", "search": "O([2])", "binary_search": "O([3])"}

Drag options to blanks, or click blank then click option'

A1

Bn

Clog n

Dn²

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up the complexities for search and binary search.

Using O(n²) which is too slow for these operations.

Access is O(1), search in unsorted list is O(n), and binary search is O(log n).