CodeBlanks Logo Icon CodeBlanks
Login Register

Time complexity

Learn how runtime grows with input size.

Time complexity

An algorithm's time complexity describes how its running time grows as the input size increases. Larger input means longer runtime.

For example, scanning an array of n elements takes n steps; doubling the input doubles the time.

Growth rate

Different algorithms have different growth rates. One may halve the input each step, another may visit every element.

The growth rate determines the difference on large inputs. A lower growth rate means a more efficient algorithm overall.

Practice Array sum

Write array_sum(arr). Sum elements and return. Print 10 with print(array_sum([1, 2, 3, 4])).

Starter code

solution.py
def array_sum(arr):
    # Sum elements

Sample solution

solution.py
def array_sum(arr):
    # Sum elements
    total = 0
    for x in arr:
        total = total + x
    return total
print(array_sum([1, 2, 3, 4]))

Expected output

10

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 What does time complexity measure?

  • Runtime growth Correct answer
  • Memory usage
  • Lines of code
  • Compile time

Explanation: Time complexity measures runtime growth.

2 Growth rate

Question 
A lower growth rate means a more ____ algorithm.
Answer 
A lower growth rate means a more efficient algorithm.

Explanation: efficient is right.

3 Time complexity: match the terms

Term Meaning
Time complexity Runtime growth
Input size n
Growth rate Efficiency
Big-O Notation

All lessons in Beginner

1 What is an algorithm?

  1. Algorithm definition
  2. Algorithm properties
  3. Pseudocode
  4. Summary - Algorithm concept

2 Big-O notation

  1. Time complexity
  2. Big-O definition
  3. Comparing complexities
  4. Summary - Big-O

3 Array

  1. What is an array?
  2. Array access
  3. Looping over an array
  4. Summary - Arrays

4 Linear search

  1. Linear search idea
  2. Implementing search
  3. Best and worst case
  4. Summary - Linear search

5 Search project

  1. Project: Overview
  2. Grades array setup
  3. Search function
  4. Print the result

6 Bubble sort

  1. Bubble sort idea
  2. One pass
  3. Full sort
  4. Summary - Bubble sort

7 Selection sort

  1. Selection sort idea
  2. Finding the minimum
  3. Swapping
  4. Summary - Selection sort

8 Insertion sort

  1. Insertion sort idea
  2. Shifting
  3. Placement
  4. Summary - Insertion sort

9 Sorting project

  1. Project: Overview
  2. Price array
  3. Apply sorting
  4. Print the result

10 Recursion basics

  1. What is recursion?
  2. Base case
  3. Recursive step
  4. Summary - Recursion

11 Fibonacci

  1. Fibonacci sequence
  2. Recursive Fibonacci
  3. Call tree
  4. Summary - Fibonacci

12 Factorial

  1. Factorial definition
  2. Recursive factorial
  3. Choosing the base case
  4. Summary - Factorial

13 Recursion project

  1. Project: Overview
  2. Recursive power
  3. Combination
  4. Print the results

14 Binary search

  1. Binary search idea
  2. Left right pointers
  3. Base case
  4. Summary - Binary search

15 Linked list

  1. What is a linked list?
  2. Node definition
  3. Traversing the list
  4. Summary - Linked list

16 Stack

  1. What is a stack?
  2. Push and pop
  3. Peek and is_empty
  4. Summary - Stack

17 Queue

  1. What is a queue?
  2. Enqueue and dequeue
  3. Front and back
  4. Summary - Queue

18 Hash table

  1. What is a hash table?
  2. Hash function
  3. Collision
  4. Summary - Hash table

19 Set

  1. What is a set?
  2. Add and lookup
  3. Intersection and union
  4. Summary - Set

20 Beginner final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4