1
Q
What time complexity is:
linear search
binary search
A
O(n)
O(log n)
2
Q
What is the maximum number of items accessed when searching for a particular item from a list using a binary search?
A
2^(n) > length of the list
n is the max number of items
Computing Theory
flashcards
Decks in class (102)
# Cards
-
4.5.1 Number systems6
-
4.1.1.2 Programming concepts13
-
4.1.1.6 Constants and variables in a programming language3
-
4.1.1.9 Exception handling3
-
4.1.1.10 Subroutines (procedures/functions) and 4.1.1.11 Parameters of subroutines9
-
4.1.1.13/14 Local variables in subroutines / Global variables in a programming language5
-
4.2.1.2 Single- and multi-dimensional arrays (or equivalent)2
-
4.2.1.3 Fields, records and files4
-
4.4.1.2 Following and writing algorithms2
-
4.4.2.1 Finite state machines (FSMs) without output2
-
4.5.2.1 Number base2
-
4.12.1.3 Function application and 4.12.1.4 Partial function application2
-
4.5.5.2 ASCII and Unicode6
-
4.5.5.3 Error checking and correction9
-
4.5.6.2 Analogue and digital and 4.5.6.3 Analogue/digital conversion7
-
4.5.6.4 Bitmapped graphics8
-
4.5.6.7 Digital representation of sound7
-
4.5.6.8 Musical Instrument Digital Interface (MIDI)5
-
4.5.6.9 Data compression6
-
4.5.6.8 Encryption6
-
4.6.1.1 Relationship between hardware and software and 4.6.1.2 Classification of software13
-
4.6.1.3 System software and 4.6.1.4 Role of an operating system (OS)10
-
4.6.2.1 Classification of programming languages7
-
4.7.1.1 Internal hardware components of a computer13
-
4.7.3.1 The processor and its components8
-
4.7.3.2 The Fetch-Execute cycle and the role of registers within it4
-
4.7.3.3 The processor instruction set3
-
4.7.3.7 Factors affecting processor performance9
-
4.7.4.1 Input and output devices7
-
4.7.4.2 Secondary storage devices15
-
4.8.1 Individual (moral), social (ethical), legal and cultural issues and opportunities30
-
4.9.1.1 Communication methods10
-
4.9.1.2 Communication basics9
-
4.9.2.1 Network topology8
-
4.4.2.2 Maths for regular expressions11
-
4.9.2.3 Wireless networking18
-
4.6.3.1 Types of program translator8
-
4.2.6.1 Hash tables5
-
4.9.3.1 The Internet and how it works14
-
4.9.3.2 Internet security9
-
4.9.4.1 TCP/IP9
-
4.1.1.3 Arithmetic operations in a programming language1
-
4.2.1.4 Abstract data types/data structures12
-
4.13.1 Aspects of software development6
-
4.1.1.15 Role of stack frames in subroutine calls4
-
4.1.2.1 Programming paradigms5
-
4.1.2.3 Object-oriented programming15
-
4.2.1.1 Data structures1
-
4.1.2.2 Procedural-oriented programming2
-
4.2.3.1 Stacks6
-
4.2.2.1 Queues4
-
4.2.4.1 Graphs9
-
4.2.5.1 Trees6
-
4.2.8.1 Vectors2
-
4.3.1.1 Simple graph-traversal algorithms3
-
4.3.2.1 Simple tree-traversal algorithms3
-
4.3.3.1 Reverse Polish – infix transformations2
-
4.3.4 Searching algorithms2
-
4.3.5 Sorting algorithms3
-
4.3.6.1 Dijkstra’s shortest path algorithm1
-
4.10.1 Conceptual data models and entity relationship modelling1
-
4.10.3 Database design and normalisation techniques5
-
4.10.2 Relational databases7
-
4.10.4 Structured Query Language (SQL)7
-
4.5.4.6 Absolute and relative errors3
-
4.5.4.1 Unsigned binary and 4.5.4.3 Signed binary using two’s complement5
-
4.5.4.7 Range and precision6
-
4.5.4.8 Normalisation of floating point form2
-
4.5.4.9 Underflow and overflow6
-
4.9.2.2 Types of networking between hosts6
-
4.9.4.2 Standard application layer protocols6
-
4.9.4.3 IP address structure1
-
4.9.4.4 Subnet masking1
-
4.9.4.5 IP standards1
-
4.9.4.6 Public and private IP addresses2
-
4.9.4.7 Dynamic Host Configuration Protocol (DHCP)3
-
4.9.4.8 Network Address Translation (NAT)2
-
4.9.4.9 Port forwarding1
-
4.9.4.10 Client server model5
-
4.9.4.11 Thin- versus thick-client computing4
-
4.7.2.1 The meaning of the stored program concept1
-
4.4.1.3 Abstraction and 4.4.1.4 Information hiding5
-
4.7.3.4 Addressing modes2
-
4.7.3.6 Interrupts3
-
4.10.5 Client server databases6
-
4.6.4.1 Logic gates5
-
4.4.1.5 Procedural abstraction and 4.4.1.6 Functional abstraction and 4.4.1.7 Data abstraction and 4.4.1.8 Problem abstraction/reduction4
-
4.4.1.9 Decomposition and 4.4.1.10 Composition2
-
4.4.1.11 Automation1
-
4.4.2.3 Regular expressions and 4.4.2.4 Regular language11
-
4.4.3.1 Backus-Naur Form (BNF)/syntax diagrams4
-
Skeleton Program21
-
4.4.5.1 Turing machine5
-
4.4.4.1 Comparing algorithms3
-
4.4.4.2 Maths for understanding Big-0 notation and 4.4.4.3 Order of complexity8
-
4.4.4.5 Classification of algorithmic problems2
-
4.4.4.6 Computable and non-computable problems and 4.4.4.7 Halting problem3
-
4.11.1 Big Data7
-
4.12.1.1 Function type and 4.12.1.2 First-class object4
-
4.12.1.5 Composition of functions1
-
4.12.2.1 Functional language programs4
-
4.12.3.1 List processing2
