Key term
Eduqas A-Level Computer Science A500QS
Data Structures: Arrays, Records and Hash Tables
Stacks, Queues, Linked Lists and Trees
Boolean Logic and Simplification
Algorithms, Pseudo-Code and Programming Constructs
Variables, Scope, Parameters and Identifiers
Recursion and Modular Programming
Sorting Algorithms
Searching and Shortest-Path Algorithms
Big O Notation and Algorithm Efficiency
Validation, Verification and Testing
Data Compression
Programming Paradigms and Computer Languages
Topic overviewProgramming paradigms and where each is usedProcedural programmingEvent-driven and visual programmingMark-up languagesObject-oriented programming: objects, classes and methodsAmbiguity in natural language and the standardisation of languagesBackus-Naur form and syntax diagramsHigh-level and low-level languages, and choosing one
Systems Analysis, Maintenance and Documentation
Topic overviewWaterfall, Agile and approaches to systems developmentThe feasibility study, budgets and time scalesMethods of investigationAbstraction, decomposition and data flow diagramsSelecting suitable hardware and softwareAcceptance testing and methods of changeoverPerfective, adaptive and corrective maintenanceBackup and recovery proceduresUser and maintenance documentation
System Design and Human-Computer Interaction
Software Engineering Tools and Translators
Topic overviewSoftware tools for the software engineering processSoftware packages in analysis, specification, design and testingIntegrated development environmentsDebugging toolsProgram version managementCompilers, interpreters and assemblersThe stages of compilationTranslation errors and execution errors
Computing, Society and the Law
Computer Architecture, the Processor and Assembly Language
Topic overviewHardware elements and how they are connectedVon Neumann architecture and the stored program conceptThe processor: control unit, ALU and registersTypes of memory: RAM, ROM and virtual memoryCache memory and locality of referenceThe fetch-execute cycle and its registersParallel processing and the limits to parallelisationAssembly language and executing a program
Input, Output and Secondary Storage
Topic overviewInput devices and how data is capturedOutput devices and how results are presentedChoosing input and output devices for a situationVoice input, dictation and voice print recognitionMagnetic, optical and solid state storageComparing secondary storage for a purposeDisc organisation, fragmentation and defragmentation
Networks, Protocols and the Internet
Topic overviewNetworks, LANs and WANsNetwork topologies and connection hardwareNetworking standards and the layered modelIP addressing, TCP and UDPApplication protocols: HTTP, FTP, SMTP, IMAP and DHCPHandshaking and establishing a connectionWireless hardware and wireless technologiesThe internet and connected mobile devices
Data Transmission and Network Performance
Topic overviewSerial and parallel transmissionSimplex, half duplex and full duplexMultiplexing and sharing a channelCircuit, message and packet switchingPackets, headers and packet contentsNetwork collisions and collision detectionRouting traffic on a networkCalculating transfer rates and lowest cost routes
Number Systems and Binary Arithmetic
Data Types, Characters and Floating Point
Topic overviewPrimitive data typesStorage requirements for each data typeASCII and standardised character setsUnicode and multilingual encodingFloating point form: mantissa and exponentConverting between real numbers and floating pointInteger and floating point comparedTruncation, rounding and accuracy
Files, Records and File Organisation
Topic overviewThe purpose of files in data processingFiles, records and fieldsFixed and variable length fields and recordsMaster files and transaction filesSerial and sequential file accessIndexed sequential access and multi-level indexesDirect access and hashing algorithmsOverflow handling and file reorganisationFile security, backups, generations and archiving
Databases, Normalisation and Entity Modelling
SQL, Big Data and Distributed Systems
Topic overviewQuery languages and the purpose of SQLCreating tables: CREATE TABLE, data types and keysRetrieving data with SELECT, FROM and WHEREComparison operators, IN, AND, OR and sub-queriesSorting, grouping and aggregate functionsInserting, updating, deleting and joining dataThe DBMS, the data dictionary and distributed databasesBig Data, data warehousing, data mining and predictive analytics
The Operating System and Its Modes
Topic overviewThe need for an operating system and the role of the kernelManaging peripherals, processes and memory protectionThe user interface and the layers between user and hardwareDirectory structures and file attributesUtility softwareBatch processing, real time control and real time transaction systemsTypes of operating system: single-user, multi-user, multi-tasking and multi-programmingDesigning an interface for different users and environments
Interrupts, Memory Management and Scheduling
Topic overviewWhat causes an interruptInterrupt handling and the interrupt service routineInterrupt priorities and how they are allocatedPartitioning main memoryMethods of data transfer between processor and devicesBuffers and double bufferingHigh level scheduling, processor and device allocationProcess states, time-slicing, polling and threading
Types of Software System
Data Security, Cryptography and Attack
Topic overviewOnline updating and the integrity of shared filesDangers of holding personal dataClerical procedures, access levels, passwords and write protectionCryptography: its purpose, and symmetric and asymmetric keysHashing, digital signatures and certificatesCaesar and Vernam ciphers and comparing cipher strengthBiometric technologies and their limitationsThreats, damage and contingency planningMalicious software, hacking and penetration testing
Big O Notation and Algorithm Efficiency
- 7 subtopics
- 21 things to know
- Component 1
What Big O Notation and Algorithm Efficiency covers
Big O Notation and Algorithm Efficiency is examined in Component 1, Programming and System Development. It covers 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 and comparing algorithms that do the same task.
The 7 subtopics
Each one has its own page.
- What Big O notation measuresTime complexity, space complexity and worst case of an algorithm.Open →
- The common complexity classesO(log n) algorithm, O(n) algorithm and O(n log n) algorithm.Open →
- Time complexity of the sorting algorithmsWorst-case time complexity of a bubble sort, why a bubble sort is O(n²) in the worst case and worst-case time complexity of an insertion sort.Open →
- Space complexity and sorting in placeSpace complexity of a bubble sort, space complexity of an insertion sort and space complexity of a quicksort.Open →
- Time complexity of linear and binary searchWorst-case time complexity of a linear search, why a linear search is O(n) and best case of a linear search.Open →
- Deriving the complexity of a given algorithmReading Big O off the code: a single loop, nested loops, loops in sequence, a halving loop, and the rule that the most expensive part decides the whole.Open →
- Comparing algorithms that do the same taskTwo resources Big O is used to compare between algorithms and drawback that comparison hides in the hash table.Open →
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
What does Big O notation describe?
Key term
State the complexity of an algorithm whose running time does not depend on the size of the input.
Key term
State the worst-case time complexity of a bubble sort.
Key term
State the worst-case time complexity of a linear search.
Key term
How is the complexity of a single loop that runs n times found?
Key term
What does the letter n stand for in an expression such as O(n)?
Key term
Give an example of an O(1) operation.
Key term
Explain why a bubble sort is O(n²) in the worst case.
Key term
What does it mean to say a sorting algorithm works in place?
Key term
Explain why a linear search is O(n).
Key term
State the complexity of a loop nested inside another loop, each running n times.
Key term
State the two resources Big O is used to compare between algorithms.
Key term
Why does Big O ignore constant factors?
Key term
What growth does O(log n) describe?
Key term
State the best-case complexity of a bubble sort that stops when a pass makes no swaps.
Key term
State the space complexity of a bubble sort.
Key term
State the best case of a linear search.
Key term
State the complexity of three loops nested one inside another, each running n times.
Key term
Why is Big O a fair way to compare two algorithms written in different languages?
Take Big O Notation and Algorithm Efficiency further
The same content, four other ways.
Commonly confused
Pairs that lose marks when they are blurred together.
Worst case vs Average case
Worst case: describing the input arrangement causing the most work. Average case: describing a typical spread of inputs.
O(n log n) vs O(log n)
O(n log n): performing a full pass at each of log n levels. O(log n): performing one step at each level.
In-place sorting vs Sorting into a second array
In-place sorting: using O(1) extra memory. Sorting into a second array: doubling the memory required.
Questions from this topic
Each one with the model answer underneath.
- 1
What does Big O notation describe?
Model answer
Big O notation describes how the resource an algorithm needs grows as the size of its input grows. The measure is the shape of that growth, not an exact count of operations.
- 2
What does the letter n stand for in an expression such as O(n)?
Model answer
The letter n stands for the size of the input, such as the number of items in a list. Complexity is always stated in terms of that size.
- 3
Why does Big O ignore constant factors?
Model answer
A constant factor does not change the shape of the growth. An algorithm taking 3n steps and one taking 100n steps are both written O(n).
- 4
Why are lower-order terms dropped from a Big O expression?
Model answer
The highest-order term dominates the total once n is large. An algorithm taking n² + 5n + 20 steps is written O(n²).
- 5
Define time complexity.
Model answer
Time complexity is the way the number of operations an algorithm performs grows with the size of its input.
- 6
Define space complexity.
Model answer
Space complexity is the way the extra memory an algorithm needs grows with the size of its input.
What is inside Levo
Six ways to work the same material.
Big O Notation and Algorithm Efficiency revision questions
- What does Big O Notation and Algorithm Efficiency cover in Eduqas A-Level Computer Science?
- 7 subtopics: 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 and comparing algorithms that do the same task. Each one has its own page with questions and model answers.
- How is Big O Notation and Algorithm Efficiency organised?
- By the Eduqas A500QS specification, subtopic by subtopic, so it matches the order you are taught it in.
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.
Or £46 a year, about £3.83 a month. Cancel anytime.