Big o nation

Question 1

Linear Search Code

Answer 1

time: O(n), space: O(1)

Question 2

Binary Search Code

Answer 2

O(log n),space: O(1)

Question 3

Bubble Sort Code

Answer 3

Time Complexity: O(n²)
Space Complexity: O(1)

Question 4

Selection Sort Code

Answer 4

Time Complexity: O(n²)
Space Complexity: O(1)

Question 5

Insertion Sort Code

Answer 5

Time Complexity: O(n²)
Space Complexity: O(1)

Question 6

QuickSort Code

Answer 6

Time Complexity: O(nlog2(n)) on average, O(n²) for worst case
Space Complexity: O(log2(n))

Question 7

Quickselect Code

Answer 7

Time Complexity: O(n).
Space Complexity: O(n) for recursion call stack in worst case. On average : O(Log n)

Question 8

Mergesort Code

Answer 8

Time Complexity: O(nlog2(n))
Space Complexity: O(n)

Question 9

Count Sort Code

Answer 9

Time Complexity: O(n + k) where k is the range of the input.
Space Complexity: O(k)

Question 9

Binary tree

Answer 9

Time: O(logn), Space: O(logn)