Big O
)}

# Workbook

This exercise will allow you to practice identifying the time complexity of an algorithm.

## Problem 1

This function returns `True` if it finds an element, and `False` otherwise. Identify the time complexity.

``````def find_item(arr, element):
for i in range(len(array)):
if arr[i] == item:
return True
return False``````

## Problem 2

This function returns the first item in an array. Identify the time complexity.

``````def first_item(arr):
return arr[0]``````

## Problem 3

This function returns the last item in an array. Identify the time complexity.

``````def last_item(arr):
return arr[-1]``````

## Problem 4

This function returns the number of times a number appears in the array. What is the time complexity?

``````def count_occurrences(arr, num):
count = 0
for i in range(len(arr)):
if arr[i] == num:
count += 1
return count``````

## Problem 5

This loop runs `n * 5` times. What is the time complexity?

``````def increment_by(n):
result = 0
for i in range(n * 5):
result += 1
return result``````

## Problem 6

This loop runs until an even number is found. What is the time complexity?

``````def find_even(arr):
for i in arr:
if i % 2 == 0:
return i``````

## Problem 7

This function uses a nested loop to sort an array. What is the time complexity?

``````def bubble_sort(arr):
for i in range(len(arr)):
for j in range(len(arr) - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr``````

## Problem 8

A loop invokes a function called `lucas_sequence`. `lucas_sequence` uses recursion to store a sequence of numbers (similar to the Fibonacci sequence) inside `memo`. What is the time complexity of this algorithm?

``````for i in range(N + 1):
print(lucas_sequence(i))

memo = {}

def lucas_sequence(n):
# Base cases
if n == 0:
return 2
if n == 1:
return 1
# Check if the result is already in the memo
if n in memo:
return memo[n]
# Otherwise, compute the result and store it in the memo
result = lucas_sequence(n-1) + lucas_sequence(n-2)
memo[n] = result
return result``````

## Problem 9

This function takes an array and a number, and returns a new array that contains all elements of the input array that are divisible by the given number.

``````def filter_by_divisibility(arr, divisor):
new_arr = []
for i in range(len(arr)):
if arr[i] % divisor == 0:
new_arr.append(arr[i])
return new_arr``````

## Problem 10

This function takes a number and calculates its factorial using recursion.

``````def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)``````

## Problem 11

This loop keeps running until the array's length reaches 1. Calculate the time complexity.

``````def loop_until_one(arr):
while len(arr) > 1:
arr = arr[:len(arr)//2] ## divides array size by 2``````

## Problem 12

This loop keeps running until the array's length reaches 1. Calculate the time complexity.

``````def loop_until_six(arr):
while len(arr) > 1:
arr = arr[:len(arr)//3]``````

## Problem 13

This loop keeps running until the array's length reaches 6. Calculate the time complexity.

``````def loop_until_six(arr):
while len(arr) > 6:
arr = arr[:len(arr)//3]``````

## Problem 14

This function checks if a number is present in the array using binary search.

``````def binary_search(arr, num):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == num:
return True
elif arr[mid] < num:
low = mid + 1``````

## Problem 15

This function uses recursion to compute the power of a number. What is the time complexity?

``````def power(x, n):
# Base case
if n == 0:
return 1
if n == 1:
return x
# Recursive case
if n % 2 == 0:
return power(x, n/2) ** 2
else:
return x * power(x, n-1)``````

## Problem 16

This function prints the diagonal elements in a 2D array. What is the time complexity?

``````def print_diagonal_elements(matrix):
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if i == j:
print(matrix[i][j])``````

## Problem 17

This function returns the result of three function calls. The function stops when the input reaches 1.

``````def f(n):
if n == 1:
return 1
return f(n - 1) + f(n - 1) + f(n - 1)``````

##### The Complete Spring Boot Development Bootcamp – Become a Java Web Developer

Feedback Summary
0.0
0 students
5

0%
4

0%
3

0%
2

0%
1

0%
Written Reviews
There are no written reviews yet.