Two algorithms sort the same list. One is O(n log n) and the other O(n²). Which should be chosen for a list of one million items, and why?

The O(n log n) algorithm should be chosen. A million items cost it roughly twenty million operations, against a million million for the quadratic one.

Give one reason a programmer might still choose the algorithm with the worse complexity.

A simpler algorithm is easier to write correctly and to maintain. On small or nearly sorted data it may also be faster in practice.

What does Big O fail to tell you about two algorithms in the same class?

Big O hides the constant factor, so two O(n) algorithms can differ by a factor of ten in real running time.

Why can the same algorithm have different complexities for time and for space?

Time and space are separate resources. A quicksort is O(n log n) in time and O(log n) in space, because the recursion stores far less than it processes.

Eduqas A-Level Computer Science A500QS

Data Structures: Arrays, Records and Hash Tables

Topic overview One-dimensional arrays and indexing Two- and three-dimensional arrays Manipulating arrays: insertion, deletion and searching Records and fields Arrays of records and record manipulation Hash tables, hashing and collisions Choosing and justifying a data structure

Stacks, Queues, Linked Lists and Trees

Topic overview Stacks: push, pop and the stack pointer Implementing a stack in an array Queues: enqueue, dequeue and pointers Circular queues and priority queues Linked lists: nodes, pointers and the free list Binary trees: nodes, roots and leaves Traversing linked lists and trees

Boolean Logic and Simplification

Topic overview AND, OR and NOT truth tables XOR, NAND and NOR truth tables Truth tables for combined Boolean expressions Boolean identities and rules De Morgan's laws Simplifying Boolean expressions Logical operators in programs, masking and encryption

Algorithms, Pseudo-Code and Programming Constructs

Topic overview Algorithms and how they are defined Pseudo-code conventions Flowcharts and flowchart symbols Sequence and selection Repetition: count-controlled and condition-controlled loops Counts, totals and rogue values Tracing, altering and writing algorithms

Variables, Scope, Parameters and Identifiers

Topic overview Variables and constants Self-documenting identifiers Annotation and program layout Scope of variables: local and global Lifetime of variables Procedure calling, parameters and return values Call by value and call by reference

Recursion and Modular Programming

Topic overview Recursion and the base case How recursive calls use the stack Recursive algorithms: factorial and Fibonacci Recursion compared with iteration Integer division with DIV and MOD Standard functions and standard modules User defined subprograms and modular design

Sorting Algorithms

Topic overview Why a variety of sorting algorithms is needed Bubble sort Insertion sort Quicksort Comparisons, exchanges and passes Storage space and sorting efficiency Writing and altering sort algorithms

Searching and Shortest-Path Algorithms

Topic overview Linear search Binary search Comparing linear and binary search Graphs, weights and the shortest-path problem Dijkstra's shortest-path algorithm Tracing a shortest-path algorithm by hand Choosing the right searching technique

Big O Notation and Algorithm Efficiency

Topic overview What Big O notation measures The common complexity classes Time complexity of the sorting algorithms Space complexity and sorting in place Time complexity of linear and binary search Deriving the complexity of a given algorithm Comparing algorithms that do the same task

Validation, Verification and Testing

Topic overview Validation and verification compared Types of validation check Implementing validation in an algorithm Verification techniques Validation and verification of data in databases Choosing test data Dry running, trace tables and identifying errors

Data Compression

Topic overview What data compression is and why it is used Lossless compression Lossy compression Run-length encoding Dictionary and Huffman coding Measuring compression: ratio and saving percentage Choosing a compression method

Programming Paradigms and Computer Languages

Topic overview Programming paradigms and where each is used Procedural programming Event-driven and visual programming Mark-up languages Object-oriented programming: objects, classes and methods Ambiguity in natural language and the standardisation of languages Backus-Naur form and syntax diagrams High-level and low-level languages, and choosing one

Systems Analysis, Maintenance and Documentation

Topic overview Waterfall, Agile and approaches to systems development The feasibility study, budgets and time scales Methods of investigation Abstraction, decomposition and data flow diagrams Selecting suitable hardware and software Acceptance testing and methods of changeover Perfective, adaptive and corrective maintenance Backup and recovery procedures User and maintenance documentation

System Design and Human-Computer Interaction

Topic overview Approaches to communicating with a computer Types of user interface Natural language interfaces Ambiguity in spoken input Designing an interface for its users The design review Evaluating a computer-based solution

Software Engineering Tools and Translators

Topic overview Software tools for the software engineering process Software packages in analysis, specification, design and testing Integrated development environments Debugging tools Program version management Compilers, interpreters and assemblers The stages of compilation Translation errors and execution errors

Computing, Society and the Law

Topic overview Social and economic change from computing Moral and ethical consequences Cultural change and the digital divide Codes of conduct and professional behaviour The effect of computers on employment Data protection and privacy law Computer misuse, copyright and freedom of information

Computer Architecture, the Processor and Assembly Language

Topic overview Hardware elements and how they are connected Von Neumann architecture and the stored program concept The processor: control unit, ALU and registers Types of memory: RAM, ROM and virtual memory Cache memory and locality of reference The fetch-execute cycle and its registers Parallel processing and the limits to parallelisation Assembly language and executing a program

Input, Output and Secondary Storage

Topic overview Input devices and how data is captured Output devices and how results are presented Choosing input and output devices for a situation Voice input, dictation and voice print recognition Magnetic, optical and solid state storage Comparing secondary storage for a purpose Disc organisation, fragmentation and defragmentation

Networks, Protocols and the Internet

Topic overview Networks, LANs and WANs Network topologies and connection hardware Networking standards and the layered model IP addressing, TCP and UDP Application protocols: HTTP, FTP, SMTP, IMAP and DHCP Handshaking and establishing a connection Wireless hardware and wireless technologies The internet and connected mobile devices

Data Transmission and Network Performance

Topic overview Serial and parallel transmission Simplex, half duplex and full duplex Multiplexing and sharing a channel Circuit, message and packet switching Packets, headers and packet contents Network collisions and collision detection Routing traffic on a network Calculating transfer rates and lowest cost routes

Number Systems and Binary Arithmetic

Topic overview Bits, bytes and words Binary and denary place value Hexadecimal notation Storing characters and numbers in binary Binary addition and subtraction Two's complement and sign and magnitude Logical and arithmetic shifts Overflow and underflow

Data Types, Characters and Floating Point

Topic overview Primitive data types Storage requirements for each data type ASCII and standardised character sets Unicode and multilingual encoding Floating point form: mantissa and exponent Converting between real numbers and floating point Integer and floating point compared Truncation, rounding and accuracy

Files, Records and File Organisation

Topic overview The purpose of files in data processing Files, records and fields Fixed and variable length fields and records Master files and transaction files Serial and sequential file access Indexed sequential access and multi-level indexes Direct access and hashing algorithms Overflow handling and file reorganisation File security, backups, generations and archiving

Databases, Normalisation and Entity Modelling

Topic overview Data consistency, redundancy and independence Relational databases and other database models Primary keys, foreign keys and indexes First normal form Second normal form Third normal form Entity relationship modelling User views and turning data into information

SQL, Big Data and Distributed Systems

Topic overview Query languages and the purpose of SQL Creating tables: CREATE TABLE, data types and keys Retrieving data with SELECT, FROM and WHERE Comparison operators, IN, AND, OR and sub-queries Sorting, grouping and aggregate functions Inserting, updating, deleting and joining data The DBMS, the data dictionary and distributed databases Big Data, data warehousing, data mining and predictive analytics

The Operating System and Its Modes

Topic overview The need for an operating system and the role of the kernel Managing peripherals, processes and memory protection The user interface and the layers between user and hardware Directory structures and file attributes Utility software Batch processing, real time control and real time transaction systems Types of operating system: single-user, multi-user, multi-tasking and multi-programming Designing an interface for different users and environments

Interrupts, Memory Management and Scheduling

Topic overview What causes an interrupt Interrupt handling and the interrupt service routine Interrupt priorities and how they are allocated Partitioning main memory Methods of data transfer between processor and devices Buffers and double buffering High level scheduling, processor and device allocation Process states, time-slicing, polling and threading

Types of Software System

Topic overview Open source, bespoke and off-the-shelf software Safety-critical systems Computers in weather forecasting Computer aided design and computer generated graphics Robotics and automation Control systems Expert systems The internet, intranets and search engines

Data Security, Cryptography and Attack

Topic overview Online updating and the integrity of shared files Dangers of holding personal data Clerical procedures, access levels, passwords and write protection Cryptography: its purpose, and symmetric and asymmetric keys Hashing, digital signatures and certificates Caesar and Vernam ciphers and comparing cipher strength Biometric technologies and their limitations Threats, damage and contingency planning Malicious software, hacking and penetration testing

Big O Notation and Algorithm Efficiency

Comparing algorithms that do the same task

3 things to know
Component 1

Overview

Two resources Big O is used to compare between algorithms and drawback that comparison hides in the hash table.

What you need to know

Answer each one before you reveal it.

Your recallNot started

Key term

What does Big O compare, why is the comparison fair between languages, and should an O(n log n) or an O(n²) algorithm be chosen for a million items?

Key term

State the two resources Big O is used to compare between algorithms.

Key term

Why is Big O a fair way to compare two algorithms written in different languages?

Questions from this subtopic

Each one with the model answer underneath.

1
State the two resources Big O is used to compare between algorithms.
Model answer
Big O compares execution time and memory requirement.
2
Why is Big O a fair way to compare two algorithms written in different languages?
Model answer
Big O measures the algorithm rather than the implementation. The language, compiler and processor affect the constant factor only.
3
Two algorithms sort the same list. One is O(n log n) and the other O(n²). Which should be chosen for a list of one million items, and why?
Model answer
The O(n log n) algorithm should be chosen. A million items cost it roughly twenty million operations, against a million million for the quadratic one.
4
Give one reason a programmer might still choose the algorithm with the worse complexity.
Model answer
A simpler algorithm is easier to write correctly and to maintain. On small or nearly sorted data it may also be faster in practice.
5
What does Big O fail to tell you about two algorithms in the same class?
Model answer
Big O hides the constant factor, so two O(n) algorithms can differ by a factor of ten in real running time.
6
Why can the same algorithm have different complexities for time and for space?
Model answer
Time and space are separate resources. A quicksort is O(n log n) in time and O(log n) in space, because the recursion stores far less than it processes.

See the rest and revise

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.

1Closed book

2Open book

3Closed book

The 3-step method, run for you

Answer cold, learn it, then prove it stuck. Levo tracks the jump between your first attempt and your last.

Data Structures: Arrays, Records and Hash Tables

Stacks, Queues, Linked Lists and Trees

Boolean Logic and Simplification

Algorithms, Pseudo-Code and Programming Constructs

Cram a whole paper in one sitting

Sort every topic into what you know and what you do not, then drill only the weak ones.

KDW to HAT.

decryptsencryptscompresses

Blank Blitz makes facts automatic

Rapid timed gap-fills on the terms and numbers you need to recall without thinking.

AThe two are not the same.

BOpen source refers to the availability of the code.

CMuch open source software is free of charge.

Build It gets the exam shape right

Assemble a full-mark answer from its marking points, in the order an examiner wants them.

Backup means the copy of the data.

TrueFalse

Test It catches misconceptions

Spot the fault in a statement. The traps are the mistakes students actually make.

721941163128510

Brain Breaks between sessions

Short focus games to reset attention, so the next set lands better than the last.

Every question in Big O Notation and Algorithm Efficiency, on a schedule.

Attempt a question from memory, write the correct version, then attempt it again. Levo records the jump between your first attempt and your last, and brings each question back on the day you are due to forget it.

Start revising, £5 a month See how the method works

Or £46 a year, about £3.83 a month. Cancel anytime.