L3 91908 Topic

Complexity and Tractability

Complexity and Tractability is about how hard or easy it is for computers to solve problems, especially as the size of the problem increases.

Key Concepts:

Tractable problems: Can be solved in a "reasonable" time (polynomial time, or P class).
Intractable problems: Take too long to solve as they grow (e.g., exponential time).
NP problems: Solutions are easy to check but hard to find.
NP-complete: Problems that are the hardest in NP—if we solve one quickly, we can solve all NP problems quickly.

Algorithms/Mechanisms:

Brute-force algorithms: Try all possibilities (often slow).
Greedy or heuristic algorithms: Give good-enough answers quickly.
Big-O notation: Measures how time/space grows with input size.

Examples of Use:

Scheduling tasks (e.g., timetables, delivery routes)
Cryptography
Puzzle-solving (like Sudoku)
Pathfinding in maps or games

Key Issues:

Some important problems can't be solved quickly (yet).
Approximations, heuristics, or limits (like timeouts) are used to deal with this.
If P = NP is solved, it would change everything (especially in security).

Human Impact & Perspectives:

Algorithms help with efficiency but may limit options or fairness (e.g., route planning, resource allocation).
Debate over using “good enough” solutions vs. “perfect” ones.
Insights into how humans tackle similar complex problems differently.

RESOURCES FOR L3 COMPLEXITY & TRACTABILITY

Teacher Help

Dr Tim Bell ran a webinar at the start of 2025 to help teachers understand Computer. The recording of this can be found on Youtube L3 External - Complexity and Tractability Webinar

This online webinar looks at what the general topic is about, and some specific learning activities that you can use with your students to engage them with the key concepts in the topic.

Task 1 - Understand Complexity & Tractability

First you need to understand what Complexity & Tractability entails.

The GOAT: The CSField Guide: Complexity & Tractability Watch the video and read through the material. If you learn this stuff inside out and you'll smash it.

Task 2 - Understanding Polynomial Vs Non-deterministic Polynomial Time Complexity

Understanding the difference between polynomial and non-deterministic polynomial time is essential when analysing how efficient or tractable an algorithm is.

Polynomial Time (P)

Definition:

An algorithm runs in polynomial time if its running time can be expressed as a power of the input size n, like:

O(n)
O(n²)

Characteristics:

Efficient / Tractable: Generally considered practical and solvable in reasonable time.
Grows predictably as input increases.
Examples:
- Linear Search – O(n)
- Bubble Sort – O(n²)
- Dijkstra’s Algorithm – O(n²)

Non-Deterministic Polynomial Time (NP, Exponential, etc.)

Definition:

An algorithm runs in non-deterministic polynomial time if its time complexity grows faster than any polynomial function of the input. Common types:

Exponential: O(2ⁿ)
Factorial: O(n!)

Characteristics:

Inefficient / Intractable for large inputs
Time explodes rapidly as n increases
Often used in brute-force solutions, puzzles, optimisation problems

Examples:

Travelling Salesman Problem (Brute Force) – O(n!)
Subset Sum (Brute Force) – O(2ⁿ)
Hamiltonian Path Search – O(2ⁿ * n)

NP stands for Nondeterministic Polynomial time, but that name is often more confusing than helpful.

CLARITY

P problems are problems where a normal deterministic algorithm can find a solution in polynomial time.

NP problems are problems where, if someone gives you a possible solution, a deterministic algorithm can check whether that solution is correct in polynomial time.

The word deterministic means the computer follows one definite sequence of steps. Given the same input, it follows the same process and produces the same result.

For example, suppose you have a route through 150 cities and someone claims:

“This route visits every city once and is shorter than 2,000 km.”

A deterministic computer can check that claim fairly quickly:

Does the route visit every city?
Does it visit each exactly once?
What is the total distance?
Is it less than 2,000 km?

That checking process is efficient.

The difficult part is finding such a route in the first place.

The “nondeterministic” idea is theoretical. Imagine a magical computer that could somehow guess the correct solution immediately, then use an ordinary deterministic algorithm to check it efficiently. NP is the class of problems that such a machine could solve in polynomial time.

REMEMBER IT AS:

P = we can find and check the solution efficiently.
NP = we can check a proposed solution efficiently, but we do not necessarily know how to find one efficiently.

Common exam errors to avoid:
NP does not mean “non-polynomial” and it does not mean “impossible for computers.”

Remember:

Every problem in P is technically also in NP, because if you can find a solution efficiently, you can certainly check one efficiently. The famous unresolved question is whether P = NP.

Comparison Table

Feature Polynomial Time Non-Polynomial Time

Notation O(n), O(n²), O(n³) O(2ⁿ), O(n!), O(n^n)

Efficiency Efficient (scales well) Inefficient (scales poorly)

Used in Sorting, searching, graphs Puzzles, encryption, AI games

Examples Merge sort, BFS TSP, brute-force knapsack

Tractability Tractable (solvable) Intractable for large n

QUIZ 1 - 91908 Complexity & Tractability — 1. Foundations

The Concept - Big O Notations

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

Big O notation is a way to describe the upper bound of an algorithm's time or space complexity in terms of input size. It essentially tells you how much the algorithm's resource usage (time or memory) grows as the input size grows.

https://discusschool.com/uploads/default/original/1X/5c70f54a8b2023459516f174b741417323329c9f.jpeg

Task 3 Simplifying Big O Notation

Process

1. Drop Constants

Keep: O(n)

Drop: O(3n) → Simplifies to: O(n)

Reason: As n grows, multiplying by a constant doesn't change the growth rate.

2. Keep the Dominant Term

Keep: O(n²)

Drop: O(n² + n + 1) → Simplifies to: O(n²)

Reason: n² dominates n and constants as input grows.

3. Different Growth Rates Have Different Classes

Expression Simplified Big O Growth Rate Type

O(n + log n) O(n) Linear

O(n² + n log n) O(n²) Quadratic

O(2n + 1000) O(n) Linear

O(n * 2ⁿ) O(n·2ⁿ) Exponential

Have a go at the question to the right->

Time Complexity

Time complexity refers to how the runtime of an algorithm increases as the size of the input increases.
It is a way of analysing the efficiency of an algorithm in terms of the number of operations it performs.

Example:
An algorithm with O(N) time complexity will take twice as long if the input size doubles.
Common Notations:
- O(1) – Constant time (independent of input size)
- O(n) – Linear time
- O(log n) – Logarithmic time
- O(n²) – Quadratic time
- O(2ⁿ) – Exponential time
- O(n!) – Factorial time

Space Complexity

Space complexity measures the amount of memory an algorithm uses as the input size grows.
This includes memory used by variables, data structures, call stacks, and function calls.

Example:
An algorithm that creates an array proportional to the input size has O(n) space complexity.
Includes:
- Input storage (if copied)
- Auxiliary data structures (like stacks, queues, hash maps)
- Recursive call memory (call stack)

Task 4 Determining Big O Notation from Algorithm types

Determining Time and Space Complexities in Big O notation

Below is a collection of code examples that demonstrate a range of common Big O notations, including O(1), O(log n), O(n!), O(n²), and O(2ⁿ).
For each code snippet:

Carefully read and understand what the algorithm is doing.
Copy the code and paste it into the Big O Complexity Calculator provided below.
Click "Calculate" to view both the Time and Space Complexity of the algorithm.

This exercise will help you build your understanding of how different algorithms scale with input size and how their performance is measured.

Accessing an Element in an Array by Index

Code Example (O(1) Complexity):

def get_first_element(arr):

if arr:

print(arr[0])

else:

print("Array is empty.")

# Example usage

data = [10, 20, 30, 40]

get_first_element(data)

Code Example (O(1) Complexity): Large data set

def get_first_element(arr):

for element in arr:

print(element)

# Example usage

large_data = list(range(1000000))

get_first_element(large_data)

Bubble Sort Algorithm

Code Example O(N²) Quadratic Time Complexity):

def bubble_sort(data):

for _ in range(len(data)): # O(n)

for i in range(len(data) - 1): # nested O(n)

if data[i] > data[i + 1]:

data[i], data[i + 1] = data[i + 1], data[i]

return data

Binary Search

Code Example O(log N) Logarithmic Time Complexity):

def binary_search(arr, target):

low = 0

high = len(arr) - 1

while low <= high:

mid = (low + high) // 2

if arr[mid] == target:

return mid # Target found

elif arr[mid] < target:

low = mid + 1 # Search right half

else:

high = mid - 1 # Search left half

return -1 # Target not found

# Example use

sorted_list = [1, 3, 5, 7, 9, 11, 13]

result = binary_search(sorted_list, 9)

print("Index:", result)

Fibonacci number

Code Example O(2^N) Exponential Time Complexity):

def nth_fibonacci(n: int) -> int:

if n in [1, 2]:

return 1

return nth_fibonacci(n - 1) + nth_fibonacci(n - 2)

Brute Force TSP

Code Example O(N!) Factorial Time Complexity):

import itertools

# Distance matrix for 4 cities

distances = [

[0, 10, 15, 20],

[10, 0, 35, 25],

[15, 35, 0, 30],

[20, 25, 30, 0]

]

def calculate_total_distance(path, distance_matrix):

total = 0

for i in range(len(path) - 1):

total += distance_matrix[path[i]][path[i + 1]]

total += distance_matrix[path[-1]][path[0]] # Return to start

return total

def tsp_brute_force(distance_matrix):

n = len(distance_matrix)

cities = list(range(n))

min_distance = float('inf')

best_path = []

for perm in itertools.permutations(cities[1:]): # Fix the first city to reduce duplicate cycles

current_path = [0] + list(perm)

current_distance = calculate_total_distance(current_path, distance_matrix)

if current_distance < min_distance:

min_distance = current_distance

best_path = current_path

return best_path, min_distance

path, distance = tsp_brute_force(distances)

print("Best Path:", path)

print("Shortest Distance:", distance)

Quick Sort

Code Example O(log N) Logarithmic Time Complexity):

def quicksort(arr):

if len(arr) <= 1:

return arr # Base case

pivot = arr[0]

left = [x for x in arr[1:] if x < pivot] # Elements less than pivot

right = [x for x in arr[1:] if x >= pivot] # Elements greater or equal

return quicksort(left) + [pivot] + quicksort(right)

# Example use

array = [9, 3, 7, 1, 6, 2, 8]

sorted_array = quicksort(array)

print(sorted_array)

Note: This Calculator is a online widget (Answers seem correct but use caution)

Use this link if the widget is not working https://www.bigocalc.com/

QUIZ 2 - 91908 Complexity & Tractability — 2. Big O

QUIZ 3- 91908 Complexity & Tractability — 3. Algorithm Analysis

Task 5 - Understanding Best Case, Worst Case, and Average Case in Big O Notation

When analysing an algorithm’s performance, we use Big O notation to describe how its running time or space requirements grow as input size increases. We often consider three different scenarios:

Best Case

Definition: The scenario where the algorithm performs the minimum number of operations.

Worst Case

Definition: The scenario where the algorithm takes the maximum possible time.

Average Case

Definition: The expected performance over all possible inputs of a given size.

Linear Search

BEST CASE

- If the item you're searching for is the first element, the algorithm finishes in → O(1) time.

WORST CASE

- If the item is at the end of the list or not present → O(n) time.

AVERAGE CASE

- On average, the item will be found halfway through the list → O(n/2), simplified to O(n).

Bubble Sort

BEST CASE

- Already sorted; only one pass needed (no swaps) → O(n) time

WORST CASE

- Reversed list; requires maximum comparisons/swaps → O(n²) time.

AVERAGE CASE

- Random data; many passes and comparisons/swaps → O(n²) time.

Generate all Permutations

BEST CASE

- All permutations must be generated → O(n!) time.

WORST CASE

- No difference—algorithm always performs factorial steps → O(n!).

AVERAGE CASE

- Still generates every permutation → O(n!).

Selection Sort

BEST CASE

- Still compares every pair (no early exit) → O(n²) time.

WORST CASE

- Still checks all remaining elements for each current index → O(n²) time.

AVERAGE CASE

- Always performs the same number of comparisons → O(n²) time.

QUIZ 4 - 91908 Complexity & Tractability — 4. Best, Worst & Average Case

Solving the Unsolvable using Heuristics and Approximation algorithms

In computer science, some problems are too complex or time-consuming to solve exactly within a reasonable time — especially those with non-polynomial time complexity like O(2ⁿ) or O(n!). This is where approximation and heuristic methods come in.

Approximation Method

An approximation algorithm gives a solution that is close to optimal, but not always exact.
Used when:

An exact solution is too slow
You need a "good enough" answer quickly

Example:

Travelling Salesman Problem (TSP) – Finding the shortest path visiting every city once is O(n!). An approximation algorithm like Nearest Neighbour can give a route that’s close to the best, in polynomial time.

Heuristic Method

A heuristic is a rule-of-thumb or strategy that guides problem-solving without guaranteeing the best solution.
Heuristics often:

Use simplifying assumptions
Are fast and adaptive
Work well in real-world or NP-hard problems

Example:

Bin Packing Problem – A heuristic like First-Fit Decreasing (FFD) places items in bins efficiently, but not perfectly.
A* pathfinding algorithm – uses heuristics to estimate distance to the goal and guide the search efficiently.

Nearest Neighbor Heuristic

How it works:

Start at any location.
Go to the nearest unvisited location.
Repeat until all locations are visited.
Return to the starting point (if needed).

Why it works:
It’s fast and easy — always picks the shortest next leg.

Limitations:
Can make locally good choices that are globally inefficient.

Real-World Use Cases:

Local Delivery Routing (Courier, Food, or Postal Services)
Hotel Housekeeping or Maintenance Rounds
Warehouse Order Picking
Tourist Navigation or Sightseeing Tours

Greedy Heuristic

How it works:

Calculate the value-to-weight ratio for each item.
Sort items in descending order of value-to-weight ratio.
Starting with the highest ratio, add as much of each item as possible to the knapsack.
Repeat until the knapsack is full.

Why it works:

It always takes the most valuable “bang for your buck” at each step.
Simple and very fast: time complexity is O(n log n) due to sorting.

Limitations:

Only works optimally for the fractional knapsack problem (where you can take parts of items).
For the 0/1 knapsack (where items must be taken whole or not at all), this approach can be very inefficient and miss the best combination.

Real-World Use Cases:

Loading Cargo (eg Airlines)
Online Shopping Discounts
Resource Allocation in Cloud Computing
Emergency Supply Distribution

A* Search Heuristic

A* is a pathfinding and graph traversal algorithm that uses heuristics to efficiently find the shortest path from a start node to a goal node. It is widely used in artificial intelligence, games, GPS navigation, and robotics.

A* balances two things:

Cost from the start to the current node — g(n)
Estimated cost from the current node to the goal — h(n) (heuristic)

It evaluates nodes based on:

f(n)=g(n)+h(n)f(n) = g(n) + h(n) f(n)=g(n)+h(n)

Where:

f(n) is the total estimated cost of the cheapest solution through node n
g(n) is the cost so far
h(n) is the heuristic estimate of the cost to the goal

Why It Works:

It prioritises paths that appear more promising.
If the heuristic is admissible (never overestimates), A* will always find the shortest path.
It is much faster than brute-force algorithms like Dijkstra’s for many practical problems.

Limitations:

Can be slow for very large or dense graphs if the heuristic is not well-designed.
Needs a good heuristic function to be efficient.
Can use a lot of memory, as it stores many nodes in memory during execution.

Real-World Use Cases:

PS Navigation Finding shortest driving routes
Games (e.g. AI agents) Enemy or NPC pathfinding
Robotics Autonomous robot movement
Logistics Route planning in warehouses

Ant Colony Optimisation

How it works:

Simulate artificial ants moving through the problem space (e.g. cities in a route).
Each ant builds a path based on two things:
- Pheromone trails (previously good paths)
- Heuristic values (e.g. distance between cities)
After all ants complete a route:
- Pheromone is deposited on shorter/better routes.
- Pheromone evaporates over time (to avoid over-committing to early bad paths).
In the next iteration, ants are more likely to follow stronger pheromone trails — encouraging collaborative learning.
This process repeats for many cycles, gradually improving the overall solution.

Why it works:

- Mimics how real ants find efficient paths between the nest and food.
- Encourages exploration early, but shifts to exploitation of good solutions over time.
- Works well for complex optimisation problems like TSP and scheduling.

Limitations:

- Slow to converge compared to some heuristics.
- May get stuck in local optima if pheromone trails become too dominant early.
- Requires fine-tuning of many parameters (evaporation rate, ant count, influence of pheromone vs distance, etc.).

Real-World Use Cases:

Vehicle routing & logistics
Network routing
Scheduling in manufacturing
Pathfinding in robotics and games

QUIZ 5 - 91908 Complexity & Tractability — 5. Heuristics & Approximation

Task 6 - Practical applications

2024 Example

The Mobile Surgical Unit (Te Waka Hauora) is a modern, fully equipped operating theatre, designed and built to be used for a wide range of day surgeries. The unit travels throughout New Zealand. It can provide low-risk elective day surgeries in rural communities that do not have local access to a full operating theatre. In 2021–2022, the service operated in 28 locations across the country.

The Mobile Surgical Unit (Te Waka Hauora) proposes to increase its destinations from 28 areas to travel to all small urban areas with populations of 1,000 to 9,999. There are 152 small urban areas in
New Zealand.

The unit wants to visit each community only once, and to minimise overall travel distance, time, and associated costs.

Someone suggests using a computer to brute-force calculate the optimal route.

(f) Using your understanding of complexity and tractability, explain and discuss:

· what type of problem this is

· whether it is tractable or not

· how the problem could potentially be solved

· whether it is possible to find the optimal solution using the brute-force approach.

QUIZ 6 - 91908 Complexity & Tractability — 6. Applied Tractability

Above resource from 2024 NZQA L3 Exam

Task 7 - QUIZ

What is the time complexity of a brute-force algorithm for solving the Travelling Salesman Problem (TSP) with n destinations?
a) O(n)
b) O(n²)
c) O(2ⁿ)
d) O(n!)

Which of the following best describes the space complexity of storing all possible paths in a brute-force TSP solution?
a) O(n)
b) O(log n)
c) O(n!)
d) O(n²)

The Mobile Surgical Unit wants to visit 152 towns only once, finding the most efficient route. Why is this considered an NP-hard problem?
a) Because the solution is always the same regardless of input
b) Because the number of possibilities grows quadratically
c) Because it has no solution
d) Because the number of possible solutions grows faster than any polynomial and no known algorithm can solve all cases in polynomial time

P vs NP Questions

Explain what is meant by the P vs NP question, and how it relates to the TSP.

If P = NP were proven true, what would this mean for solving the Mobile Surgical Unit’s routing problem?

Best, Worst, and Average Case Questions

Describe the best-case scenario for a heuristic algorithm solving the Mobile Surgical Unit route problem.

What would the worst-case scenario look like for a brute-force solution?

Check Your answers

What is the time complexity of a brute-force algorithm for solving the Travelling Salesman Problem (TSP) with n destinations?
a) O(n)
b) O(n²)
c) O(2ⁿ)
d) O(n!)

Which of the following best describes the space complexity of storing all possible paths in a brute-force TSP solution?
a) O(n)
b) O(log n)
c) O(n!)
d) O(n²)

P vs NP Questions

Explain what is meant by the P vs NP question, and how it relates to the TSP.

Sample answer:
The P vs NP question asks whether every problem that can be verified in polynomial time (NP) can also be solved in polynomial time (P).
The TSP is in NP, because if someone gives you a proposed route, you can quickly check if it meets the length requirement. However, we don’t know how to find that route in polynomial time. If P ≠ NP, then no efficient algorithm exists to solve TSP for all cases.

If P = NP were proven true, what would this mean for solving the Mobile Surgical Unit’s routing problem?

Sample answer:
It would mean there exists a polynomial-time algorithm that can find the optimal route for the TSP. The Mobile Surgical Unit could then compute the shortest route to all 152 towns efficiently. However, most experts believe that P ≠ NP, so heuristic or approximation methods are more realistic.

Best, Worst, and Average Case Questions

Describe the best-case scenario for a heuristic algorithm solving the Mobile Surgical Unit route problem.

Sample answer:
The best case is when the heuristic (e.g. Nearest Neighbour) accidentally finds the optimal route or a very close approximation with minimal computation. This can happen if the town layout is simple and well-aligned with the heuristic's assumptions.

(Without checking all n! permutations (where n = 152), we have no guarantee that the route found is the shortest. In real-world scenarios, this is usually impractical due to the factorial time complexity of brute-force solutions, so we settle for "good enough" rather than proven optimal. )

What would the worst-case scenario look like for a brute-force solution?

Sample answer:
The worst case is when the number of towns is large (like 152), and the algorithm has to check every possible permutation of the route—O(n!) combinations. This would take billions of years, making it completely infeasible.

Task 8 - Relate this concept to humans and comparing and contrasting different perspectives

Humans deal with complex problems all the time — from planning travel to scheduling tasks — and we often do so without formal algorithms. Instead of brute-force solutions, we rely on heuristics, intuition, and experience to make decisions quickly and effectively.

This mirrors what computers do when faced with intractable problems: when exact methods (e.g. brute force with O(n!)) are too slow, we switch to approximations and heuristics.

Comparing Perspectives on Complexity

Perspective Approach Strengths Limitations

Human (Intuitive) Uses judgment, past experiences Fast, flexible, includes emotion/context Prone to bias, hard to replicate or verify

Heuristic Algorithm Uses rules of thumb or shortcuts Efficient, scalable, consistent No guarantee of optimal solution

Exact Algorithm Explores all possible options Always finds the best answer Often too slow or resource-heavy

Consider this Scenario

Scenario:

A courier company like NZ Post or CourierPost needs to plan delivery routes for vans across a city or rural region. Each van must deliver parcels to dozens of addresses efficiently in a single day.

What could a human approach be?

- What are the benefits and limitations of this approach

What could a Computer Science approach be?

What type of problem is this?
What is the Big O notation?
Would this work?
What are the benefits and limitations of this approach

What could a Heuristic approach be?

What heuristics could be used?
Explain how the heuristic you considered actually works for this scenario.

Check your answers

Human Approach

The driver might rely on familiar routes, local traffic knowledge, or just “what feels right.”
They might choose to:
- Avoid roads they know are busy.
- Cluster deliveries by suburb.
- Prioritise regular customers.

Limitation: The route may not be the shortest or most fuel-efficient, but it’s fast to decide, and “good enough.”

Computer Science Approach

A software system could try to optimally plan the shortest possible route using exact algorithms — essentially solving a version of the Travelling Salesman Problem (TSP).
However, for 50+ delivery points, the number of possible routes is enormous: O(n!).

Brute-force becomes intractable – even supercomputers would take too long.

Heuristic Algorithm Approach

Instead, the system uses a heuristic like:

Nearest Neighbour
1. Start at the courier depot or the first delivery location.
2. From the current location, find the closest unvisited delivery address.
3. Travel to that address and mark it as delivered.
4. Repeat step 2 until all deliveries are completed.
5. Optionally, return to the depot (if the route is required to end at the start point)

These give good, fast solutions that drivers can follow in real-time, balancing efficiency and practicality.

QUIZ 7 - 91908 Complexity & Tractability — 7. Final Diagnostic

Teacher Note

DTTA will provide one at the start of Term 3. This will be advertised on the DTTA Mobilse forum.

This the DTTA Derived Grade Exam Resources for 91908 provided in 2024

Sit a Derived Grade Exam

Your teacher will provide this. Do your best and remember to give specific examples!

COMPLEXITY & TRACTABILITY — Post-Exam Sharpen Up

What we need to sharpen

The biggest errors were not usually calculations. They were misunderstanding what Big O tells us, confusing P/NP, and assuming a heuristic either finds the perfect answer or is simply guessing.

Common misconceptions and errors

Big O describes how resource requirements grow as input size grows.
It does not tell you the exact runtime in seconds.
Ignore constant factors and lower-order terms:

O(3n) → O(n)
O(n² + 50n + 2000) → O(n²)

Polynomial algorithms such as O(n³) are normally considered tractable, even though they may still become slow for very large inputs.

Know common patterns

O(1) constant
O(log n) logarithmic
O(n) linear
O(n²) quadratic
O(2ⁿ) exponential
O(n!) factorial

Do not mix these up simply because an algorithm has “two things happening”.

Best and worst case

Linear search:
- best case = first item → O(1)
- worst case = search through list → O(n)
Optimised Bubble Sort:
- already sorted best case → O(n)
- typical worst case → O(n²)
If an algorithm always generates every permutation, the input arrangement does not magically make it O(n) — the enumeration is still approximately O(n!).

P and NP

A recurring misconception was:

“NP means computers cannot solve the problem.”

That is not the definition.

A useful distinction is:

P: solutions can be found in polynomial time.

NP: a proposed solution can be checked in polynomial time.

NP-complete: problems in NP that are among the hardest problems in NP.

Heuristics

A heuristic is not just random guessing.

It gives a practical method for finding a good solution quickly without necessarily guaranteeing the optimal solution.

Nearest neighbour, for example, makes a locally attractive choice. Those local choices can result in a poor final route.

Remember:

g(n) = cost already travelled
h(n) = estimated cost remaining
f(n) = g(n) + h(n)

QUICK TECHQUITY TASK QUESTION

For each algorithm below, identify its likely complexity and explain WHY:

accessing array[0]
scanning every item once
two nested n-sized loops
binary search
Bubble Sort
simple recursive Fibonacci
brute-force Travelling Salesman.

Then answer:

A company has 150 delivery locations.

Explain why brute force is impractical and why the company might deliberately choose a heuristic even though it cannot guarantee the mathematically shortest route.

ANSWER

Algorithm Complexity

Accessing array[0] — O(1)

Accessing a known position in an array takes approximately the same amount of work regardless of how many items are in the array. The computer can directly access position 0, so increasing the size of the array does not increase the number of steps needed.

Scanning every item once — O(n)

If there are n items, the algorithm performs approximately one operation for each item. If the number of items doubles, the amount of work approximately doubles.

Two nested n-sized loops — O(n²)

The outer loop runs n times, and for each of those iterations the inner loop also runs n times. This produces approximately n × n operations, so the complexity is O(n²).

Binary Search — O(log n)

Binary search checks the middle item of a sorted list and then eliminates approximately half of the remaining search space each time. Because the amount of data still needing to be searched repeatedly halves, the number of steps grows logarithmically.

Bubble Sort — O(n²)

Bubble Sort repeatedly compares neighbouring items and swaps them when they are in the wrong order. In a typical or worst-case situation, it may make approximately n comparisons across n passes, giving O(n²).

An optimised Bubble Sort can have a best case of O(n) if the list is already sorted and the algorithm stops after completing a pass with no swaps.

Simple Recursive Fibonacci — approximately O(2ⁿ)

A simple recursive Fibonacci algorithm calculates values by repeatedly calling something like fib(n-1) and fib(n-2). These calls create more recursive calls, causing the number of calculations to grow extremely quickly as n increases.

Brute-force Travelling Salesman — approximately O(n!)

A brute-force Travelling Salesman solution tries the possible orders in which the locations could be visited and compares the resulting routes. As more locations are added, the number of possible orderings grows factorially, approximately O(n!).

150 Delivery Locations

A company has 150 delivery locations and wants to find the shortest possible route.

A brute-force algorithm would attempt to examine an enormous number of possible route orderings. For 150 locations, the search space grows approximately as 150!, which is an unimaginably large number of possible routes.

This means that even a very fast computer could not realistically check every possible route and then select the shortest one within a useful amount of time.

Why use a heuristic?

Instead, the company could use a heuristic, such as nearest neighbour, to find a good route quickly.

A nearest-neighbour approach might repeatedly travel to the closest location that has not yet been visited. This dramatically reduces the amount of searching required.

The trade-off is that a heuristic does not guarantee the mathematically shortest possible route. A locally good decision early in the route may lead to a less efficient route later.

However, the company may deliberately accept this because a very good route calculated in seconds or minutes is much more useful than waiting an unrealistic amount of time for the guaranteed optimal route.

The key trade-off is:

Exact solution = guaranteed optimum but potentially impractical runtime.

Heuristic = practical runtime and a good solution, but no guarantee of the optimum.

Good luck for the exam!

DERIVED GRADE EXAM

Page updated

Google Sites

Report abuse