Algorithms and Problem SolvingAlgorithms and Problem Solving
Characterising computational problems, generate-and-test, solvability and complexity classes (P, NP, NP-hard, NP-complete), Big O time/space analysis, design techniques (divide and conquer, greedy, dynamic programming, backtracking) and standard sorting, searching and graph traversal algorithms.
3.7 Commonly Used Algorithms · Reviewed lesson · version 1 · published 16 Nov 2026
Algorithms are essential tools in computer science and are applied to a wide range of problems, from sorting data to searching for information in large datasets. Some algorithms are foundational, serving as building blocks for more complex operations. This section explores some of the most commonly used algorithms, including sorting, searching, and graph traversal algorithms.
3.3.1 Solvable vs. Unsolvable Problems · Reviewed lesson · version 1 · published 16 Nov 2026
In computer science, problems are classified as solvable or unsolvable based on whether there exists an algorithm that can provide a solution.
Solvable Problems: A problem is considered solvable if an algorithm can solve it within a finite amount of time. These problems have clearly defined inputs and outputs, and there is a step-by-step procedure to reach the solution.
Example: Calculating the greatest common divisor (GCD) of two integers is a solvable problem. The Euclidean algorithm provides a clear and finite method to determine the GCD, making it a classic example of a solvable problem.
Unsolvable Problems: On the other hand, a problem is unsolvable if no algorithm can be created that will provide a solution in all cases. These problems do not have a general procedure that can guarantee a solution for every possible input.
Example: The Halting Problem is a famous example of an unsolvable problem. It involves determining whether a given program will eventually halt (finish running) or continue to run forever. Alan Turing proved that no general algorithm can solve the Halting Problem for all possible program-input pairs, making it a fundamental example of an unsolvable problem.
3.7.2.2 Binary Search · Reviewed lesson · version 1 · published 16 Nov 2026
Images and handouts: 0.2 MB
Binary Search is an efficient algorithm for finding an item in a sorted list. It works by repeatedly dividing the search interval in half and discarding the half where the item cannot be, until the item is found or the interval is empty.
Process:
Start with the middle element of the sorted list.
If the middle element is the target, return its position.
If the target is smaller than the middle element, repeat the search on the left half.
If the target is larger, repeat the search on the right half.
Example: Suppose you have a sorted list [1,3,5,7,9,11,13] and you are searching for the number
Binary Search will start at the middle element (7) and find the target immediately.
Complexity: The time complexity of Binary Search is O(log n), making it much faster than linear search algorithms, especially for large datasets. Figure 3.7 illustrates the binary search process, showing how the search interval is halved at each step, making the search more efficient.
3.6.2 Greedy Algorithms
3.6.2 Greedy Algorithms · Reviewed lesson · version 1 · published 16 Nov 2026
Greedy algorithms work by making a sequence of choices, each of which is locally optimal, with the hope that these choices will lead to a globally optimal solution. The greedy approach is often used when a problem has an optimal substructure, meaning that the optimal solution to the problem can be constructed from optimal solutions to its sub problems.
Example: A classic example of a greedy algorithm is the Coin Change problem. Suppose you have coins of different denominations and you want to make a specific amount with the fewest coins possible. The greedy algorithm would involve choosing the largest denomination coin that does not exceed the remaining amount, then subtracting that value and repeating the process until the desired amount is achieved.
3.2.1.3 Pros and Cons · Reviewed lesson · version 1 · published 16 Nov 2026
Images and handouts: 66 KB
Pros:
Simplicity: The Generate and Test algorithm is easy to understand and implement, making it a useful approach for simple problems.
Versatility: It can be applied to a wide range of problems, particularly when no clear solution strategy exists.
Exhaustiveness: The algorithm explores all possible solutions, ensuring that no potential solution is overlooked.
Cons:
Inefficiency: The algorithm can be highly inefficient, especially for large problem spaces, as it may require testing many possible solutions before finding a valid one.
No Optimality Guarantee: The Generate and Test algorithm does not necessarily find the optimal solution; it only guarantees a valid one. For example, in optimization problems, it may find a solution that works but is not the best possible.
Computational Expense: For problems with a vast number of potential solutions, the algorithm may become computationally expensive and impractical.
3.3.3.3 Class NP-Hard
3.3.3.3 Class NP-Hard · Reviewed lesson · version 1 · published 16 Nov 2026
NP-hard problems are a class of problems that are at least as difficult as the hardest problems in NP (Non-deterministic Polynomial time). Solving an NP-hard problem is challenging, and no efficient algorithm is known for finding a solution. These problems are usually very difficult and take a lot of time to solve, even when the cases are not very large.
Example:
A well-known example of an NP-hard problem is the Traveling Salesman Problem (TSP), we discussed in Section 3.3.2.
Why TSP is NP-Hard
No Known Efficient Solution: There is no known algorithm that can solve TSP quickly for large numbers of cities. As the number of cities increases, the number of possible routes grows factorially, making the problem extremely difficult to solve exactly.
Computational Complexity: The time required to solve TSP grows so quickly with the number of cities that it becomes impractical to compute the exact solution for large instances. For example, with just 10 cities, there are 3,628,800 possible routes.
Illustration of Complexity
To illustrate the complexity:
With 5 Cities: There are 120 possible routes.
3.1 Understanding Computational Problems
3.1 Understanding Computational Problems · Reviewed lesson · version 1 · published 16 Nov 2026
Introduction
In this chapter, we will explore how to solve problems using algorithms, which are step-by-step instructions for performing tasks. Understanding algorithms is essential not only for computer science but also for everyday problem-solving. We will start by learning what computational problems are and how to describe them clearly. Then, we will look at different types of algorithms and how they can help us solve various kinds of problems. We will also discuss how to measure the efficiency of algorithms to find the best solutions. By the end of this chapter, you'll have the skills to think systematically and create effective solutions using algorithms.
A computational problem is a challenge that can be solved through a computational process, which involves using an algorithm, i.e., a set of step-by-step instructions that a computer can execute. The objective is to find a solution by following a finite sequence of steps that a computer can perform.
3.1.1.2 Well-defined vs. ill-defined Problems
3.1.1.2 Well-defined vs. ill-defined Problems · Reviewed lesson · version 1 · published 16 Nov 2026
Images and handouts: 0.1 MB
Problems can also be categorized based on how clearly they are defined:
Well-defined Problems: These problems have clear goals, inputs, processes, and outputs. For instance, the problem of determining if a number is even, is a well-defined problem because it has a clear goal (determine if the number is even), clear input (a single integer), a clear process (check if the number is divisible by 2), and a clear output (even or odd) as shown in Figure 3.1.
Ill-defined Problems: These problems lack clear definitions or may have ambiguous goals and requirements. For instance, consider a project aimed at “improving education in Pakistan”. This goal is vague and broad. The input might include resources such as funding, teachers, and educational materials, but without clear specifications on how much funding is needed, what kind of teachers are required, or which educational materials are most effective.
Figure 3.1: Finding an Even Number (original drawing after the textbook's Figure 3.1).
3.6 Algorithm Design Techniques
3.6 Algorithm Design Techniques · Reviewed lesson · version 1 · published 16 Nov 2026
Algorithm design is a critical aspect of problem-solving in computer science. It involves creating systematic methods to solve problems efficiently and effectively. There are several well-known algorithm design techniques that help in developing robust algorithms for a variety of computational problems.
3.4.1 Time Complexity · Reviewed lesson · version 1 · published 16 Nov 2026
Time complexity is a measure of how the runtime of an algorithm increases as the size of the input data grows. It helps us understand how efficiently an algorithm performs when dealing with larger amounts of data.
Example: Consider the task of sorting a list of numbers. If the list has only a few numbers, the task might be quick. However, as the volume of numbers increases, the time required to sort them also increases. Time complexity allows us to predict how this runtime will grow as the size of the list becomes larger.
3.7.2.1 Linear Search · Reviewed lesson · version 1 · published 16 Nov 2026
A linear search is a straightforward method for finding an item in a list. You check each item one by one until you find what you're looking for. Here's how it works,
Start at the Beginning: Look at the first item in the list.
Check Each Item: Compare the item you're looking for with the current item.
Move to the Next: If they don't match, move to the next item in the list.
Repeat: Continue this process until you find the item or reach the end of the list.
Example: Suppose you have a list of city names: [Karachi, Lahore, Islamabad, Faisalabad] And you want to find out if Islamabad is in the list.
Start with Karachi. Since Karachi isn't Islamabad, move to the next city.
Next is Lahore. Lahore isn't Islamabad, so move to the next city.
Now you have Islamabad. This is the city you're looking for!
In this case, you've found Islamabad in the list. If Islamabad weren't in the list, you would check all the cities and then conclude that it's not there. This method is called a linear search because you check each item in a straight line, from start to finish.
3.7.1 Sorting Algorithms · Reviewed lesson · version 1 · published 16 Nov 2026
Sorting algorithms are used to arrange data in a particular order, such as ascending or descending. Sorting is a fundamental operation that is often a prerequisite for other tasks like searching and data analysis.
3.7.3.1 Breadth-First Search (BFS) · Reviewed lesson · version 1 · published 16 Nov 2026
Breadth-First Search (BFS) is a graph traversal algorithm that explores all the nodes of a graph level by level, starting from a given node (often called the root). It uses a queue to keep track of the nodes that need to be explored.
Process:
Start from the root node and enqueue it.
Dequeue a node, process it, and enqueue all its unvisited neighbors.
Repeat the process until the queue is empty.
Example: In a social network graph, where each node represents a person and edges represent friendships, BFS can be used to find the shortest path between two people (e.g., finding the degree of separation between two users).
Complexity: The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges. This makes it efficient for exploring large graphs.
Summary · Reviewed lesson · version 1 · published 16 Nov 2026
This chapter offers a thorough introduction to algorithms and problem-solving. It begins by defining and categorizing computational problems as solvable or unsolvable, and tractable or intractable. Key algorithmic methods such as generate and test are explained, alongside problem types like search, sorting, optimization, and decision problems. It also explores design techniques including greedy algorithms, divide and conquer, dynamic programming, and backtracking. The chapter further covers commonly used algorithms, efficiency, and complexity analysis with Big O notation. It highlights the importance of algorithmic thinking for effective problem-solving and practical implementation, emphasizing the need to evaluate and balance trade-offs based on specific problem requirements.
3.3 Problem Solvability and Complexity · Reviewed lesson · version 1 · published 16 Nov 2026
Understanding the solvability and complexity of problems is a fundamental concept in computer science. It helps us determine whether a problem can be solved using an algorithm and, if so, how efficiently it can be solved. This section explores the distinctions between solvable and unsolvable problems, as well as tractable and intractable problems, providing a foundation for understanding computational complexity.
3.7.3 Graph Algorithms · Reviewed lesson · version 1 · published 16 Nov 2026
Graph algorithms are used to explore and analyze graphs, which are data structures made up of nodes (vertices) connected by edges. These algorithms are essential for network analysis, route planning, and social network analysis.
3.4 Algorithm Analysis · Reviewed lesson · version 1 · published 16 Nov 2026
Algorithm analysis is the process of determining the computational complexity of algorithms, which includes their time and space complexity. This analysis helps predict the algorithm's performance and is crucial for selecting the best algorithm for a particular task.
3.5.2 Scalability · Reviewed lesson · version 1 · published 16 Nov 2026
Scalability refers to an algorithm's ability to maintain its efficiency as the size of the input data grows. An algorithm that scales well will perform efficiently even when the input data is significantly larger than what it was initially designed for.
3.3.3.1 Class P · Reviewed lesson · version 1 · published 16 Nov 2026
Class P refers to a category of problems that can be solved efficiently by a computer. In simpler terms, these are problems where a computer can find a solution quickly, even as the size of the problem grows: problem grows.
Example: Let's consider a simple problem: sorting a list of numbers.
Suppose you have the following list:
[4, 1, 3, 2, 5]
The goal is to arrange these numbers in ascending order:
[1, 2, 3, 4, 5]
Class P and Sorting
Easy to Solve: The sorting problem can be solved efficiently by a computer. As the list gets larger, the time required to sort it increases at a manageable rate.
Polynomial Time: This means the time needed grows in a predictable and reasonable way. Example: Doubling the size of the list results in roughly double the time needed.
Deterministic Algorithm: Sorting uses a set of clear steps or a recipe. For instance, the algorithm compares and swaps numbers to sort the list. Following these steps always leads to the correct result if done correctly.
How It Works
3.6.3 Dynamic Programming
3.6.3 Dynamic Programming · Reviewed lesson · version 1 · published 16 Nov 2026
Dynamic Programming (DP) is an optimization technique used to solve problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant calculations. DP is particularly useful for problems with overlapping subproblems and optimal substructure.
Example: The Fibonacci sequence is a well-known example where DP can be applied. Instead of recalculating Fibonacci numbers repeatedly, DP stores the results of each Fibonacci number as it is computed, allowing the algorithm to retrieve these values directly when needed, significantly reducing the number of calculations.
Fibonacci sequence
The Fibonacci sequence is a series of numbers that starts with 0 and 1. Each subsequent number in the sequence is found by adding the two preceding numbers. Here's how it works:
Start with 0 and 1.
Add them together to get the next number: 0 + 1 = 1.
Now add the last two numbers in the sequence: 1 + 1 = 2.
Continue this pattern: 1 + 2 = 3, and so on.
So the Fibonacci sequence begins like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so forth. It is named after Leonardo of Pisa, who is also known as Fibonacci, and it appears in many interesting places in nature, such as the pattern of leaves on a stem, the branching of trees, and even the arrangement of a pine cone's scales.
3.1.1.1 Classifying Computational Problems
3.1.1.1 Classifying Computational Problems · Reviewed lesson · version 1 · published 16 Nov 2026
Computational problems can be classified into different categories based on their characteristics and the methods required to solve them. Some common classifications include:
Decision Problems: Problems where the output is a simple “yes” or “no”.
Search Problems: Problems where the task is to find a solution or an item that meets certain criteria.
Optimization Problems: Problems where the goal is to find the best solution according to some criteria.
Counting Problems: Problems where the objective is to count the number of ways certain conditions can be met.
3.4.2 Space Complexity · Reviewed lesson · version 1 · published 16 Nov 2026
Space complexity measures how the amount of memory or space an algorithm uses changes as the size of the input data increases. It helps us understand how efficiently an algorithm uses memory when dealing with larger amounts of data.
Example: if an algorithm needs to store a list of numbers, its space complexity tells us how much memory will be required as the volume of numbers increases.
Why Space Complexity Matters
Understanding space complexity is important because it helps us gauge the memory requirements of an algorithm. Efficient use of memory is crucial, especially for large-scale applications or systems with limited memory resources.
How Space Complexity is Analyzed
Space complexity is typically expressed using Big O notation, similar to time complexity. It describes the upper limit on the amount of memory an algorithm will use as the input size grows. Here are some common examples:
O(1) Constant Space: The algorithm uses a fixed amount of memory regardless of the input size. For example, a simple algorithm that only needs a few variables to store intermediate values has constant space complexity.
O(n) Linear Space: The memory usage grows linearly with the size of the input. For instance, if an algorithm needs to store a list of items, the amount of memory required increases directly with the number of items.
O(n²) Quadratic Space: The memory usage grows quadratically as the size of the input increases. For example, an algorithm that needs to store a matrix of size n x n will have quadratic space complexity, as the number of elements in the matrix increases with the square of n.
3.3.3 Complexity Classes (P, NP, NP-hard, NP-complete) · Reviewed lesson · version 1 · published 16 Nov 2026
Understanding the complexity of problems involves classifying them into different categories based on their solvability and the time required to solve them.
3.2.1.1 Definition and Process · Reviewed lesson · version 1 · published 16 Nov 2026
The Generate and Test algorithm involves two main steps:
Generate: In this step, the algorithm generates possible solutions to the problem. These solutions can be generated randomly, systematically, or based on some heuristic.
Test: After generating a potential solution, the algorithm tests it against the problem's requirements or constraints. If the solution satisfies all the conditions, it is considered valid. If not, the algorithm generates a new solution and repeats the process.
3.3.2 Tractable vs. Intractable Problems · Reviewed lesson · version 1 · published 16 Nov 2026
Once a problem is determined to be solvable, the next consideration is its computational complexity—how efficiently it can be solved. Problems are categorized as tractable or intractable based on the resources required (time and space) to solve them.
Tractable Problems: A problem is considered tractable if it can be solved in polynomial time, denoted as P. Polynomial time means that the time taken to solve the problem increases at a manageable rate (as a polynomial function) relative to the size of the input. Tractable problems are considered "efficiently solvable."
Example: Sorting a list of numbers using algorithms like Merge Sort or Quick Sort is a tractable problem because these algorithms have a polynomial time complexity of O(n log n), where n is the number of elements in the list.
Intractable Problems: Intractable problems are those that require super-polynomial time to solve, often growing exponentially with the size of the input. These problems are impractical to solve for large inputs because the time required becomes unmanageable.
Example: The Travelling Salesman Problem (TSP), where the goal is to find the shortest possible route that visits a set of cities and returns to the origin, is an example of an intractable problem. The problem is NP-hard, meaning that as the number of cities increases, the number of possible routes grows factorially, making it infeasible to solve exactly for large instances. Factorially means, multiplying all whole numbers from n down to 1.
For 2 cities: 2! = 2 x 1=2 possible routes.
3.2 Algorithms for Problem Solving
3.2 Algorithms for Problem Solving · Reviewed lesson · version 1 · published 16 Nov 2026
Algorithms are step-by-step procedures for solving problems, much like a recipe provides steps for cooking a dish. They form the backbone of computer science, enabling machines to perform tasks efficiently. Understanding algorithms is essential because they provide the logic behind software operations, allowing us to solve complex problems, optimize performance, and ensure accuracy in various applications.
3.1.1 Characterizing Computational Problems · Reviewed lesson · version 1 · published 16 Nov 2026
To solve a problem computationally, we need to understand its characteristics. This involves identifying the inputs, the desired outputs, and the process needed to transform the inputs into outputs.
3.7.2 Search Algorithms · Reviewed lesson · version 1 · published 16 Nov 2026
Search algorithms are designed to find specific elements or a set of elements within a dataset. They are critical for tasks such as information retrieval, database queries, and decision-making processes.
3.7.3.2 Depth-First Search (DFS) · Reviewed lesson · version 1 · published 16 Nov 2026
Images and handouts: 0.1 MB
Depth-First Search (DFS) is another graph traversal algorithm that explores as far down a branch as possible before backtracking to explore other branches. It uses a stack to manage the nodes to be explored.
Process:
Start from the root node and push it onto the stack.
Pop a node, process it, and push all its unvisited neighbors onto the stack.
Repeat the process until the stack is empty.
Figure 3.8: Comparison of BFS and DFS (original drawing after the textbook's Figure 3.8).
Example: DFS can be used in solving puzzles like mazes, where the algorithm explores one possible path to the end, and if it hits a dead end, it backtracks and tries another path.
Complexity: The time complexity of DFS is O(V+E), similar to BFS. However, DFS is more memory-efficient for deep graphs, while BFS is more suited for shallow graphs.
Figure 3.9 compares the BFS and DFS algorithms, showing how BFS explores a graph level by level, while DFS explores as far as possible down each branch before backtracking.
3.2.1 Generate and Test Algorithm
3.2.1 Generate and Test Algorithm · Reviewed lesson · version 1 · published 16 Nov 2026
The Generate and Test algorithm is a straightforward and intuitive problem-solving approach commonly used in artificial intelligence and computer science. This algorithm works by generating potential solutions to a problem and then testing each one to determine if it meets the required conditions. The process continues until a satisfactory solution is found or all possible solutions have been exhausted.
3.7.1.1 Bubble Sort · Reviewed lesson · version 1 · published 16 Nov 2026
Bubble Sort is one of the simplest sorting algorithms. It works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. This process is repeated until the list is sorted.
Process:
Start from the beginning of the list.
Compare each pair of adjacent elements.
Swap them if they are in the wrong order.
Continue the process until no more swaps are needed.
Example: Consider the list [5,3,8,4,2]. Bubble Sort will compare 5 and 3, swap them, then move to the next pair, and so on. After several passes through the list, the algorithm will sort the list as [2,3,4,5,8].
Complexity: The time complexity of Bubble Sort is O(n²), making it inefficient for large datasets. However, it is easy to understand and implement, making it useful for educational purposes and small datasets.
3.4.1.1 Big O Notation · Reviewed lesson · version 1 · published 16 Nov 2026
Images and handouts: 96 KB
Big O notation is a mathematical way to describe the time complexity of an algorithm. It provides an upper bound on the time an algorithm will take to complete as the input size grows. This notation helps in comparing the efficiency of different algorithms by giving a clear picture of their performance.
How Big O Notation Works
Big O notation uses symbols to describe how the runtime of an algorithm changes with the size of the input. Here are some common examples:
O(1) Constant Time: The runtime does not change with the size of the input. For instance, accessing a specific item in an array by its index is constant time because it takes the same amount of time regardless of the array size.
O(n) Linear Time: The runtime grows linearly with the size of the input. For example, consider a scenario where there are n students in a college, each with a unique student ID. If we need to find a specific student by searching through the list of all n students, the time it takes to find the student will depend on the number of students we have to check. In the worst-case scenario, the student we are looking for might be the very last one on the list, meaning we would have to check all n students. This process involves examining each student one by one, making the search take a time proportional to n. Therefore, this example represents a linear time complexity O(n), where the time taken increases directly with the number of students.
O(n²) Quadratic Time: The runtime grows quadratically as the size of the input increases. For instance, consider a scenario where n students in a college are participating in a programming competition, and we want to compare the performance of each pair of students to determine the best team. To do this, we must compare each student with every other student. The number of comparisons required is the sum of the first n - 1 integers, which can be approximated as
3.3.3.2 Class NP
3.3.3.2 Class NP · Reviewed lesson · version 1 · published 16 Nov 2026
Images and handouts: 60 KB
Class NP refers to a category of problems for which, if a solution is given, it can be checked quickly by a computer. These are problems where verifying a proposed solution is easy, but finding that solution might be difficult and time-consuming.
Example:
Consider a common example of solving a Sudoku puzzle. In Sudoku, you fill a 9 x 9 grid with numbers so that each row, column, and 3 x 3 sub grid contains all digits from 1 to 9 exactly once as shown in Figure 3.5.
Class NP and Sudoku
Verification is Easy: If someone gives you a completed Sudoku grid, you can quickly check if the solution is correct. You just need to ensure that each row, column, and 3 x 3 sub grid contains all numbers from 1 to 9 without repeating.
Finding the Solution is Hard: Solving Sudoku from scratch, especially larger or more complex puzzles, can be difficult and time-consuming. There is no simple, fast way to guarantee a solution, which means finding the solution is not always efficient.
Non-deterministic Polynomial Time: Class NP problems can be solved quickly if given a correct solution, but finding that solution might take an impractically long time for large problems.
How It Works
In the context of Sudoku:
3.6.4 Backtracking
3.6.4 Backtracking · Reviewed lesson · version 1 · published 16 Nov 2026
Backtracking is a method used in solving problems where you build up a solution step by step. If you find that a particular path doesn't lead to a solution, you simply go back and try a different path. It's like trying out different routes on a map and turning back if you find that you're going the wrong way. This method is often used for problems where you need to look at all possible options, like with puzzles or problems that involve different combinations.
3.7.1.2 Selection Sort · Reviewed lesson · version 1 · published 16 Nov 2026
Selection Sort is another simple sorting algorithm. It works by selecting the smallest (or largest, depending on the desired order) element from the unsorted part of the list and swapping it with the first element of the unsorted part. This process is repeated for the remaining unsorted portion of the list.
Process:
Find the minimum element in the unsorted part of the list.
Swap it with the first unsorted element.
Move the boundary of the sorted and unsorted sections by one element.
Repeat the process for the remaining elements.
Example: For the list [29,10,14,37,13], Selection Sort will first find the smallest element, 10, and swap it with 29. The list becomes [10,29,14,37,13]. The process continues until the list is fully sorted.
Complexity: The time complexity of Selection Sort is O(n²). Like Bubble Sort, it is not efficient for large datasets but is straightforward to implement.
3.5.1 Efficiency · Reviewed lesson · version 1 · published 16 Nov 2026
Algorithm efficiency refers to how well an algorithm uses resources like time and space (memory) to solve a problem. The efficiency of an algorithm is typically evaluated based on its time complexity (how the run time increases as the input size increases) and space complexity (how the memory usage grows as the input size increases).
Example: Consider two sorting algorithms: Bubble Sort and Merge Sort. Bubble Sort has a time complexity of O(n²), meaning that if the input size doubles, the time taken increases by four times. Merge Sort, however, has a time complexity of O(n log n), which grows much more slowly as the input size increases, making it more efficient for large datasets.
3.5.3 Suitability for Specific Problems · Reviewed lesson · version 1 · published 16 Nov 2026
Not all algorithms are suitable for all types of problems. The choice of algorithm depends on the problem's specific requirements, such as the need for speed, memory usage, or the nature of the data.
Example: Imagine you're looking for a book in a small, unorganized collection. The best way is to check each book one by one, this is a Linear Search. Now, if your books are neatly arranged alphabetically on a shelf, you can quickly find the book by starting in the middle and deciding which half to search, this is a Binary Search.
3.3.3.4 NP-Complete · Reviewed lesson · version 1 · published 16 Nov 2026
Images and handouts: 95 KB
NP-Complete problems are a special subset of NP problems that are both in NP and as hard as the hardest problems in NP. This means that these problems are particularly challenging, and if you can solve one NP-Complete problem efficiently, you can solve all problems in NP efficiently.
Example: A classic example of an NP-Complete problem is the Knapsack Problem.
The Knapsack Problem
In the Knapsack Problem, you have a knapsack with a maximum weight capacity and a set of items, each with a weight and a value. The goal is to determine the most valuable combination of items to put in the knapsack without exceeding its weight capacity.
Why the Knapsack Problem is NP-Complete
Verification is Easy: If you are given a set of items and a proposed solution, you can quickly check if the total weight is within the knapsack's capacity and if the total value is correct.
Solving the Problem is Hard: Finding the optimal combination of items to maximize the total value while staying within the weight limit is challenging, especially as the number of items increases.
NP-Completeness: The Knapsack Problem is NP-Complete because it is both in NP (you can verify a solution quickly) and as hard as the hardest problems in NP. If you could solve the Knapsack Problem efficiently, you could solve all NP problems efficiently.
3.6.1 Divide and Conquer
3.6.1 Divide and Conquer · Reviewed lesson · version 1 · published 16 Nov 2026
Images and handouts: 77 KB
Figure 3.6: Merge Sort Process (original drawing after the textbook's Figure 3.6).
Divide and Conquer is a powerful algorithm design technique that works by breaking a large problem into smaller, more manageable parts. Each smaller part is solved independently, and then their solutions are combined to solve the original problem, as shown in Figure 3.6. This approach is particularly effective for problems that can be divided into similar smaller problems, making it easier to find a solution step by step.
Example: Merge Sort is a classic example of a Divide and Conquer algorithm. The algorithm begins by dividing an unsorted list into two halves. Each half is then sorted independently, and finally, the two sorted halves are merged together to create the final sorted list. Figure 3.6 illustrates the process of Merge Sort, showing how the list is divided and then combined to produce a sorted output. This visualization highlights the efficiency of the Divide and Conquer approach.
Figure 3.7: Binary Search Process (original drawing after the textbook's Figure 3.7).
The Generate and Test algorithm is often used in AI applications, such as game playing and problem-solving, where the solution space is large, and the best approach is to try different possibilities until one works!
Figure 3.2: Flowchart of the Generate and Test Algorithm Process (original drawing after the textbook's Figure 3.2).
To sort the list [4, 1, 3, 2, 5], a computer might follow these steps:
Compare the first number with the second number. Swap them if needed.
Move to the next pair and repeat the process.
Continue until the entire list is sorted.
The time required to sort the list grows at a manageable rate as the list size increases. For example, going from 5 numbers to 10 numbers will increase the time, but it remains within a reasonable limit.
O(log n) Logarithmic Space: The memory usage grows logarithmically, meaning it increases very slowly relative to the input size. For instance, some algorithms that use divide-and-conquer strategies may have logarithmic space complexity because they only need to store a small portion of the data at each step.
. Thus, the time complexity for this task is quadratic, represented as O(n²). The time taken increases quadratically as the number of students n increases.
O(log n) Logarithmic Time: The runtime grows logarithmically, meaning it increases very slowly relative to the input size. For example, imagine a scenario where you are playing a guessing game with n students in a college. One student thinks of a number between 1 and n, and your task is to guess the number. After each guess, the student will tell you whether the actual number is higher or lower than your guess. By starting in the middle of the range and adjusting your guess based on the feedback, you can quickly narrow down the possible numbers. The number of guesses required to find the correct number is proportional to the number of times you can halve the range, which is logarithmic in nature. Therefore, the time complexity of this guessing process is O(log n).
Big O Notation: growth of O(1), O(log n), O(n) and O(n²) (original drawing after the textbook's graph).
When comparing different time complexities, it's essential to understand how the time required for an algorithm grows as the size of the input n increases. Constant time, represented as O(1), remains unchanged regardless of the size of n. This means that no matter how large the input is, the time taken will be the same, as seen by the flat line in the graph.
Checking a Solution: To verify if a Sudoku solution is correct, you can quickly check each row, column, and subgrid to ensure they all have numbers 1 through 9 without repetition. This verification process is straightforward and efficient.
Solving the Puzzle: Finding the correct arrangement of numbers for a Sudoku puzzle can be challenging. There are many possible configurations, and determining the correct one involves lot of trial and error or advanced algorithm.
Figure 3.3: A simple Sudoku Puzzle (original drawing after the textbook's Figure 3.3).
To illustrate why the Knapsack Problem is NP-Complete:
Small Instances: For a small number of items, it might be feasible to find the optimal solution by checking all possible combinations.
Larger Instances: As the number of items grows, the number of possible combinations increases exponentially, making it impractical to solve the problem by brute force
Figure 3.4: Venn diagram of the complexity classes P, NP, NP-hard, and NP-complete (original drawing after the textbook's Figure 3.4).
Figure 3.4 shows a Venn diagram of the complexity classes P, NP, NP-hard, and NP-complete. It visually represents the relationships between these classes, highlighting how some problems can be solved efficiently, while others pose significant challenges to computational theory.