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)

---

This workbook was created by Jad and Rayan Slim. Feel free to explore some of their courses:

The Complete Java Development Bootcamp

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