Comparing and evaluating algorithms

விளையாடிக் கற்றுக்கொள்ளுங்கள்

ஆற்றல் சம்பாதிக்க இந்த கேள்விகளுக்குப் பதிலளியுங்கள், பின்னர் மீன் பிடித்து ஆராயுங்கள். கணக்கு தேவையில்லை.

கல்வியாளர்களுக்கு: Comparing and evaluating algorithms (KS3 Computing, Computer Science)-க்கான தயாரான பாட ஸ்லைடுகள், திருப்புதல் குறிப்புகள் — உங்கள் பாடத்தில் அவற்றைப் பயன்படுத்தவும், அல்லது கற்பவர்கள் நேரலை விளையாட்டாக விளையாடும் ஊடாடும் வகுப்பு செயல்பாடாக தலைப்பை இயக்கவும்.

பாட குறிப்புகள்

What is Algorithm Analysis?

Algorithm analysis is the process of finding how much time and memory an algorithm needs to run.
It helps us compare different algorithms that solve the same problem, so we can choose the best one.
The amount of time is called time complexity; the amount of memory is called space complexity.
We usually measure complexity based on the size of the input, often called n.
An algorithm is efficient if its resource use is small or grows slowly as the input size grows.
Analysis can be done theoretically (using maths) or empirically (by running the program), but theoretical is more general.

Why Compare Algorithms?

For the same problem, there can be many different algorithms (e.g., searching a list: linear vs binary search).
We compare them on correctness: does the algorithm always give the right answer?
We compare them on number of steps: how many operations does it take?
We compare them on memory used: how much storage does it need?
A faster algorithm may use more memory, so we must trade off time and space.
Choosing the right algorithm can make a program run in seconds instead of hours.

Time Complexity Basics

Time complexity is the number of steps an algorithm takes as the input size n grows.
We often describe it using Big O notation, e.g., O(n) for linear time, O(log n) for logarithmic time.
O(1) means constant time: the algorithm takes the same number of steps regardless of input size.
O(n) means the steps grow proportionally to the input size (e.g., linear search).
O(log n) means the steps grow slowly, like binary search on a sorted list.
O(n²) means steps grow with the square of the input size (e.g., simple sorting algorithms like bubble sort).

Space Complexity Basics

Space complexity is the amount of memory an algorithm uses, also measured with Big O.
It includes memory for the input, temporary variables, and any extra data structures.
An algorithm that sorts a list in place uses O(1) extra space.
An algorithm that creates a copy of the list uses O(n) extra space.
Sometimes a faster algorithm needs more memory, so we must consider the trade-off.

Best, Worst and Average Case

The same algorithm can behave differently on different inputs of the same size.
Best case: the input that causes the fewest steps (e.g., searching for the first item in a list).
Worst case: the input that causes the most steps (e.g., searching for an item that is not present).
Average case: the typical number of steps over all possible inputs.
When we say an algorithm's complexity, we usually mean the worst case.
Worst case is useful because it guarantees the algorithm will finish within a certain time.

Comparing Search Algorithms

Linear search checks each item in a list one by one; it is O(n).
Binary search repeatedly halves a sorted list; it is O(log n).
Binary search is much faster for large lists, but it requires the list to be sorted.
For a list of 1,000,000 items, linear search may take up to 1,000,000 steps, while binary search takes about 20 steps.
If the list is unsorted, you must sort it first, which adds extra time.
So the best algorithm depends on the situation.

Comparing Sorting Algorithms

Bubble sort repeatedly swaps adjacent items; it is O(n²) in the worst case.
Merge sort divides the list and merges sorted halves; it is O(n log n).
For large lists, merge sort is much faster than bubble sort.
Merge sort uses extra memory for merging, while bubble sort sorts in place.
Simple algorithms like bubble sort are easier to understand and code.
Efficient algorithms like merge sort are better for large data sets.

Empirical vs Theoretical Analysis

Empirical analysis means running the program and measuring time/memory on specific inputs.
It is easy to do but only gives results for the inputs you tested.
Theoretical analysis uses maths to predict performance for any input size.
Theoretical analysis is independent of the computer, programming language, and implementation.
Empirical results can be misleading if you test on a fast computer with a slow algorithm and a slow computer with a fast algorithm.
Theoretical analysis gives a fair comparison between algorithms.

Choosing the Right Algorithm

Consider the size of the input: for small inputs, a simple algorithm may be fine.
Consider correctness: always choose an algorithm that is proven correct.
Consider time and space trade-offs: sometimes a faster algorithm uses more memory.
Consider ease of implementation: simpler algorithms are less error-prone.
Consider the data structure: e.g., binary search needs a sorted array.
Always test with realistic data to confirm the theoretical analysis.

ஸ்லைடுகள்

Step through every slide for this topic — plus flashcards and revision notes — with a free account.

பதிவு செய்க — இலவசம்உள்நுழைக

பயிற்சி கேள்விகள்

இலவச முன்னோட்டம் — 57-இல் 8 கேள்விகள். அனைத்தையும் பார்க்க பதிவு செய்யவும்.

1.What is the main purpose of analysing algorithms?
Easy
- ATo compare the efficiency of different algorithms for the same problem
- BTo make programs longer
- CTo write algorithms in a specific programming language
- DTo debug errors in code
2.Which of these is NOT a resource that algorithm analysis typically measures?
Easy
- ATime
- BStorage
- CNumber of programmers
- DNumber of steps
3.An algorithm is said to be efficient when the function relating input size to steps has small values or grows slowly.
Easy
True or false?
4.When not otherwise specified, the function describing the performance of an algorithm is usually an upper bound determined from which type of inputs?
Medium
- ABest case
- BAverage case
- CWorst case
- DRandom case
5.Which of the following are reasons why empirical (benchmark) testing alone is insufficient to compare algorithm efficiency? (select all that apply)
Medium
- AAlgorithms are platform-independent
- BBenchmarks can be affected by hardware speed
- CIt cannot provide timing data for all infinitely many possible inputs
- DIt is too expensive to run
- EIt always gives exact theoretical complexity
6.In the uniform cost model, what is the cost of each machine operation?
Medium
- AProportional to the number of bits involved
- BConstant, regardless of the size of the numbers
- CProportional to the size of the input
- DZero for simple operations
7.The logarithmic cost model assigns a cost proportional to the number of bits involved in an operation.
Easy
True or false?
8.Which cost model is more cumbersome to use and is only employed when necessary, such as for arbitrary-precision arithmetic?
Medium
- AUniform cost model
- BUnit-cost model
- CLogarithmic cost model
- DConstant cost model

மேலும் கேள்விகள்

9.What does run-time analysis estimate?
Medium
- AThe increase in running time as input size increases
- BThe number of bugs in the code
- CThe memory used by the program
- DThe number of lines of code
10.Binary search on a sorted list of size n runs in a number of steps proportional to the square of n.
Medium
True or false?
11.Which of the following best describes the 'hidden constant' in asymptotic analysis?
Medium
- AA constant multiplicative factor relating efficiencies of reasonable implementations
- BThe number of lines of code
- CThe time taken for one operation
- DThe size of the input
12.Why might counting an addition of two numbers as one step be unwarranted in some contexts?
Medium
- ABecause numbers may be arbitrarily large, making addition time non-constant
- BBecause addition is always slower than multiplication
- CBecause computers do not perform addition
- DBecause it is too simple
13.What does the term 'space complexity' refer to?
Medium
- AThe number of storage locations used by an algorithm
- BThe amount of disk space on the computer
- CThe number of lines of code
- DThe time taken to run the algorithm
14.The term 'analysis of algorithms' was coined by Alan Turing.
Easy
True or false?
15.Which of the following notations is used to estimate complexity in the asymptotic sense?
Medium
- ABig O notation
- BBig π notation
- CBig Sigma notation
- DBig Delta notation
16.Match each cost model to its description.
Medium
- Uniform cost model
- Logarithmic cost model
- Assigns constant cost to every operation
- Assigns cost proportional to number of bits
17.Order the following steps in the typical process of analysing an algorithm's run-time:
Medium
- Define the model of computation
- Identify the input size n
- Count the number of steps as a function of n
- Express the result using asymptotic notation
18.Match each algorithm to its typical time complexity (in Big O notation) for a list of size n.
Easy
- Linear search
- Binary search
- Bubble sort
- O(n)
- O(log n)
- O(n²)
19.Arrange the following steps in the correct order for comparing two algorithms using logical reasoning.
Medium
- Identify the inputs and their sizes
- Count the number of basic operations for each algorithm
- Compare the growth of operation counts as input size increases
- Choose the algorithm with the slower growth
20.Which of the following are advantages of using logical reasoning (theoretical analysis) to compare algorithms, rather than just benchmarking them? (select all that apply)
Medium
- AIt gives results that are independent of the computer hardware.
- BIt can predict performance for very large inputs that are impractical to test.
- CIt measures the exact time in seconds for a given input.
- DIt provides a fair comparison between different algorithms.
- EIt is easier than writing a program to test.
21.An algorithm with a time complexity of O(n²) will always be slower than one with O(n) for the same input size.
Easy
True or false?
22.The term 'analysis of algorithms' was coined by:
Easy
- ADonald Knuth
- BAlan Turing
- CAda Lovelace
- DEdsger Dijkstra
23.Which of the following are reasons why empirical benchmarking alone is insufficient to compare algorithm efficiency? (select all that apply)
Medium
- AResults depend on the computer hardware.
- BResults depend on the programming language and implementation.
- CIt is impossible to test all possible inputs.
- DIt gives exact timing for all input sizes.
- EIt cannot predict performance for large inputs without testing them.
24.Which algorithm has a time complexity of O(log n)?
Easy
- AAlgorithm A
- BAlgorithm B
- CBoth
- DNeither
25.For a list of 1000 elements, binary search will always be faster than linear search.
Medium
True or false?
26.A student writes two programs to search a sorted list of 1000 names. Program 1 uses linear search and Program 2 uses binary search. Both are run on the same computer. Which statement is correct?
Medium
- AProgram 1 will always be faster for this list.
- BProgram 2 will always be faster for this list.
- CFor a list of 1000 names, binary search is guaranteed to be faster than linear search.
- DFor a list of 1000 names, binary search may be faster or slower than linear search depending on the position of the target.
27.A programmer compares two algorithms for the same problem by running them on a fast computer and a slow computer. The fast computer runs Algorithm A, the slow computer runs Algorithm B. For a small input size, Algorithm A appears much faster. What is the most likely reason this conclusion may be wrong?
Medium
- AThe fast computer has more memory.
- BAlgorithm A may have a higher asymptotic complexity, so for larger inputs it will eventually be slower.
- CAlgorithm B is written in a different programming language.
- DThe slow computer is not reliable.
28.Consider two algorithms for the same problem. Algorithm X has time complexity O(n) and Algorithm Y has time complexity O(n²). On a particular input of size 100, Algorithm X takes 10 ms and Algorithm Y takes 5 ms. What can you conclude?
Hard
- AAlgorithm X is always faster than Algorithm Y.
- BAlgorithm Y is always faster than Algorithm X.
- CThe hidden constants in the two algorithms differ, so for this input Y is faster, but for sufficiently large inputs X will be faster.
- DThe time complexity measurements are wrong.
29.A student measures the run-time of a sorting algorithm on lists of sizes 100, 200, 400, and 800, obtaining times of 1 ms, 4 ms, 16 ms, and 64 ms respectively. Which of the following statements are true? (select all that apply)
Medium
- AThe algorithm appears to have a time complexity of O(n²).
- BThe algorithm appears to have a time complexity of O(n log n).
- CWhen the input size doubles, the run-time quadruples.
- DThe run-time is proportional to the square of the input size.
- EThe algorithm is definitely quadratic.
30.In the uniform cost model, the cost of an addition operation is proportional to the number of bits in the numbers being added.
Easy
True or false?
31.Match each algorithm to its typical time complexity for a list of size n.
Medium
- Linear search
- Binary search
- Bubble sort
- O(n)
- O(log n)
32.Arrange the following steps in the correct order for comparing two algorithms using logical reasoning (theoretical analysis).
Medium
- Define the model of computation (e.g., uniform cost).
- Determine the time complexity function for each algorithm as a function of input size n.
- Use asymptotic notation (e.g., Big O) to compare the growth rates.
- Identify the worst-case input for each algorithm.
33.An algorithm processes a list of n numbers. On a particular computer, the run-time T(n) is measured and found to fit the equation T(n) = 0.001n² + 3n milliseconds. What is the dominant term for very large values of n, and what is the time complexity in Big O notation?
Hard
- A0.001n² is dominant; O(n²)
- B3n is dominant; O(n)
- C0.001n² is dominant; O(0.001n²)
- D3n is dominant; O(n²)
34.A student wants to compare the efficiency of two algorithms for the same problem. Which of the following is the most reliable method to compare them across different computers?
Medium
- AMeasure the run-time in seconds on a single computer
- BUse logical reasoning to count the number of steps as a function of input size
- CRun each algorithm on the fastest computer available
- DCount the number of lines of code in each algorithm
35.Two algorithms, A and B, solve the same problem. Algorithm A has time complexity O(n) and Algorithm B has time complexity O(log n). On a particular computer, Algorithm A takes 1 second for an input of size 1000. Approximately how long would Algorithm A take for an input of size 2000, assuming the constant factor remains the same?
Medium
- A1 second
- B2 seconds
- C4 seconds
- D0.5 seconds
36.A student measures the run-time of a sorting algorithm on lists of sizes 100, 200, 400, and 800, obtaining times of 1 ms, 4 ms, 16 ms, and 64 ms respectively. What is the likely time complexity of the algorithm?
Hard
- AO(n)
- BO(n log n)
- CO(n²)
- DO(log n)
37.Which of the following are advantages of using logical reasoning (theoretical analysis) over empirical benchmarking when comparing algorithms? (select all that apply)
Medium
- AIt can predict performance for all possible input sizes.
- BIt is independent of the programming language and hardware.
- CIt always provides exact run-time in seconds.
- DIt can compare algorithms without running them.
38.In the logarithmic cost model, the cost of an addition operation is proportional to the number of bits in the numbers being added.
Easy
True or false?
39.Match each cost model to its correct description.
Medium
- Uniform cost model
- Logarithmic cost model
- Assigns constant cost to every machine operation
- Assigns cost proportional to number of bits involved
40.Arrange the following steps in the correct order for using logical reasoning to compare two algorithms for the same problem.
Medium
- Identify the input size n.
- Count the number of steps each algorithm takes as a function of n.
- Compare the growth rates of the step counts.
- Choose the algorithm with the slower growth rate for large inputs.
41.Fill in the blanks with the correct terms.
Easy
The two common cost models are the ____ cost model and the ____ cost model.
42.Fill in the blank with the correct notation.
Medium
Binary search is said to run in ____ time, meaning its steps grow logarithmically with input size.
43.What are the three types of case descriptions that may be of interest when analysing an algorithm?
Medium
44.Fill in the blank with the correct term.
Medium
In theoretical analysis, estimates are often made for arbitrarily large input, which is called the ____ sense.
45.What is the maximum number of time units needed for binary search on a sorted list of n elements if each lookup takes unit time?
Medium
46.What does the 'space complexity' of an algorithm measure?
Medium
47.If a binary search on a sorted list of n elements takes at most log2(n) + 1 time units, what is the maximum number of time units needed for a list of 8 elements?
Medium
48.Fill in the blank: The number of steps for binary search is proportional to the ___ of the list size n.
Easy
The number of steps for binary search is proportional to the ____ of the list size n.
49.A binary search algorithm on a sorted list of n elements takes at most log₂(n) + 1 time units. What is the maximum number of time units needed for a list of 16 elements?
Medium
50.Complete the sentence.
Easy
The term "analysis of algorithms" was coined by ____.
51.A company benchmarks two sorting algorithms on the same data set. For a list of 10,000 items, Algorithm A takes 0.5 seconds and Algorithm B takes 2 seconds. However, theoretical analysis shows that Algorithm A is O(n²) and Algorithm B is O(n log n). Explain why the benchmark result might be misleading, and predict what would happen if the list size were increased to 1,000,000 items.
Medium
52.Using the uniform cost model, how many steps does it take to perform 5 additions of two numbers, if each addition is counted as one step?
Easy
53.Explain why empirical benchmarking alone is not sufficient to compare the efficiency of algorithms, using the example of linear search on a fast computer versus binary search on a slow computer.
Hard
54.Explain why counting an addition of two numbers as one step might not be a valid assumption in all contexts.
Hard
55.If a binary search on a sorted list of n elements takes at most log2(n) + 1 time units, what is the maximum number of time units needed for a list of 8 elements?
Medium
- A3 time units
- B5 time units
- C4 time units
- D6 time units
56.A binary search algorithm on a sorted list of n elements takes at most log₂(n) + 1 time units. What is the maximum number of time units needed for a list of 16 elements?
Medium
- A5 time units
- B4 time units
- C7 time units
- D6 time units
57.Using the uniform cost model, how many steps does it take to perform 5 additions of two numbers, if each addition is counted as one step?
Easy
- A5 steps
- B6 steps
- C7 steps
- D4 steps

திருப்புதல் குறிப்புகள்

## Comparing and Evaluating Algorithms When you have two algorithms for the same problem, you need to compare them. Key things to look at: - **Correctness**: Does it always give the right answer? - **Number of steps**: How many steps does it take? (time complexity) - **Memory used**: How much storage does it need? (space complexity) An algorithm is **efficient** if the number of steps or memory used is small, or grows slowly as the input size grows. ### Best, Worst, and Average Cases Different inputs of the same size can make an algorithm behave differently. So we talk about: - **Best case**: the fastest it can be - **Worst case**: the slowest it can be (usually what we care about) - **Average case**: typical behaviour Usually, when we say an algorithm's performance, we mean the **worst case** unless we say otherwise. ### Big O Notation (Simple Idea) Big O notation describes how the number of steps grows as input size `n` grows. You don't need to calculate exact numbers, just the general trend. - **O(log n)** – logarithmic time (e.g., binary search). Very fast. - **O(n)** – linear time (e.g., linear search). Steps grow directly with `n`. - **O(n²)** – quadratic time (e.g., simple sorting algorithms). Steps grow much faster. Example: Binary search on a sorted list of `n` items takes at most `log₂(n) + 1` steps (if each lookup is constant time). ### Why Not Just Test It? Testing algorithms on real computers can be misleading because: - Different computers run at different speeds. - A fast computer with a slow algorithm might beat a slow computer with a fast algorithm for small inputs, but for large inputs the fast algorithm wins. - Empirical testing can't cover all possible inputs. So we use theoretical analysis to compare algorithms fairly. ### Cost Models When counting steps, we assume each basic operation takes a constant amount of time. This is the **uniform cost model** (unit-cost model). Sometimes, for very large numbers, we use the **logarithmic cost model**, where the cost depends on the number of bits. ### Key Takeaway To compare algorithms, think about: - Correctness - Time complexity (steps) - Space complexity (memory) - Worst-case behaviour Use Big O to describe growth, and remember that theoretical analysis is better than just timing on one computer.

Algorithm: A step-by-step set of instructions to solve a problem.
Efficiency: How well an algorithm uses resources (time and memory). An algorithm is efficient if its resource use is small or grows slowly with input size.
Time complexity: The number of steps an algorithm takes as a function of the input size.
Space complexity: The amount of memory an algorithm uses as a function of the input size.
Worst-case: The scenario where an algorithm takes the most steps or uses the most memory for an input of a given size.
Best-case: The scenario where an algorithm takes the fewest steps or uses the least memory for an input of a given size.
Average-case: The typical performance of an algorithm over all possible inputs of a given size.
Big O notation: A way to describe how the runtime or memory usage of an algorithm grows as the input size grows. For example, O(log n), O(n), O(n²).
Binary search: An efficient algorithm to find an item in a sorted list. It repeatedly halves the search area, so it runs in O(log n) time.
Linear search: A simple search algorithm that checks each item in a list one by one. It runs in O(n) time.
Uniform cost model: A cost model where every machine operation is assumed to take the same constant amount of time, regardless of the size of the numbers involved.
Logarithmic cost model: A cost model where the cost of an operation is proportional to the number of bits involved. Used for very large numbers, e.g., in cryptography.

ஃப்ளாஷ் கார்டுகள்

What does 'analysis of algorithms' mean?

It is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them.

What are the two main resources measured in algorithm analysis?

Time (number of steps) and storage (memory locations used).

What is time complexity?

A function that relates the size of an algorithm's input to the number of steps it takes.

What is space complexity?

A function that relates the size of an algorithm's input to the number of storage locations it uses.

When is an algorithm considered efficient?

When the function for its resource use has small values or grows slowly compared to the growth in input size.

What are the three cases used to describe algorithm behavior for different inputs of the same size?

Best, worst, and average case.

When not specified, which case is usually used to describe an algorithm's performance?

The worst case, as an upper bound.

Who coined the term 'analysis of algorithms'?

Donald Knuth.

What is Big O notation used for?

To estimate the complexity of an algorithm for arbitrarily large input sizes, in an asymptotic sense.

What does O(log n) mean colloquially?

Logarithmic time—the number of steps grows proportionally to the logarithm of the input size.

Give an example of an algorithm that runs in O(log n) time.

Binary search on a sorted list.

What is a 'hidden constant' in asymptotic analysis?

A constant multiplicative factor that relates the efficiencies of any two reasonable implementations of the same algorithm.

Why are exact efficiency measures rarely used?

They usually require assumptions about the particular implementation, called a model of computation.

What is a model of computation?

An abstract computer or set of assumptions about which operations take unit time.

What is the uniform cost model?

It assigns a constant cost to every machine operation, regardless of the size of the numbers involved.

What is the logarithmic cost model?

It assigns a cost to every machine operation proportional to the number of bits involved.

When is the logarithmic cost model used?

When necessary, e.g., for arbitrary-precision arithmetic algorithms like those used in cryptography.

What is run-time analysis?

A theoretical classification that estimates how running time increases as input size (n) increases.

Why can't software profiling provide timing data for all possible inputs?

Because there are infinitely many possible inputs; theoretical methods are needed.

What is a drawback of empirical (benchmark) metrics for comparing algorithms?

Algorithms are platform-independent, so results vary with hardware, programming language, and operating system.

Give an example showing why empirical metrics can be misleading.

A fast computer using linear search may beat a slow computer using binary search for small lists, but for large lists binary search becomes far better.

What is the maximum number of time units needed for binary search on a sorted list of n elements, assuming unit-time lookups?

At most log2(n) + 1 time units.

Why must we be careful when counting an addition as one step?

If numbers can be arbitrarily large, the time for a single addition may not be constant.

What is the key point about published lower bounds for problems?

They are often for a restricted model of computation, so algorithms may be faster than naively thought possible.

Unlock all 57 questions, flashcards & more

இந்த தலைப்பிற்கான ஒவ்வொரு கேள்வியையும், ஸ்லைடுகளையும், ஃப்ளாஷ் கார்டுகளையும் மற்றும் திருப்புதல் குறிப்புகளையும் பார்க்க இலவச கணக்கை உருவாக்கவும்.

பதிவு செய்க — இலவசம்உள்நுழைக

முந்தைய தேர்வுகள்

இந்த தலைப்பிற்கான முந்தைய தேர்வு பயிற்சி விரைவில் வருகிறது.

விரைவில் வருகிறது