What is an algorithm?
An algorithm is a finite, precise sequence of steps that transforms input into output to solve a problem.
Study 01 Algorithm Analysis and Big-O Notation with 12 free online flashcards. Review key terms, definitions, and concepts with this interactive flashcard deck.
What is an algorithm?
An algorithm is a finite, precise sequence of steps that transforms input into output to solve a problem.
What does an abstract data type specify?
An ADT specifies the values and operations a type supports without prescribing how those operations are implemented.
What is a representation invariant?
A representation invariant is a condition that must remain true about a data structure’s internal state.
Which elements commonly support a correctness argument?
A correctness proof uses a precondition, postcondition, invariant, and termination argument to show that an algorithm produces the required result and stops.
What are the three steps for proving a loop invariant?
The three loop-invariant steps are initialization, maintenance, and termination.
Why must input size be defined precisely?
The input-size variable depends on the problem: it may count array elements, string characters, tree nodes, graph vertices, edges, or integer-representation bits.
What does time complexity measure?
Time complexity describes how the number of basic operations grows with input size; it does not usually predict exact elapsed seconds.
What does worst-case complexity measure?
Worst-case analysis measures the greatest work for any input of size n, providing a guarantee for every input of that size.
What is auxiliary space?
Auxiliary space is the additional memory used by an algorithm beyond the memory needed to store its input.
What does Big-O notation express?
Big-O gives an eventual asymptotic upper bound: for suitable constants c>0 and n0, 0≤f(n)≤cg(n) for all n≥n0.
When is a function Θ(g(n))?
A function is Θ(g(n)) when it is both O(g(n)) and Ω(g(n)), giving an asymptotically tight bound.
How do common growth classes rank from slower to faster?
From slower to faster growth, the listed classes are Θ(1), Θ(logn), Θ(n), Θ(nlogn), Θ(n2), Θ(2n), and Θ(n!).
A progressive guide to how computers encode numbers, text, images, and sound as binary data, including the trade-offs and limits of digital representation.
A focused set of flashcards covering Python variables, data types, expressions, control flow, functions, input, output, and common programming practices.
Learn how Boolean expressions, logical operators, and conditional structures let programs make reliable decisions, including how to handle boundaries, branch order, and testing.
A structured guide to the main data structures, their operations, efficiency trade-offs, representations, and practical selection criteria.
A 14-question quiz on trees, binary trees, traversals, recursive algorithms, and binary search trees. The questions progress from foundational concepts to applied reasoning about structure, complexity, and BST operations.
A structured guide to comparison-based sorting algorithms, their complexity, stability, memory use, and practical selection criteria.
A progression through how data is organized, searched, exposed through software interfaces, and managed through abstraction layers in modern computer systems.
A medium-difficulty quiz on integrating problem definition, representation, algorithms, complexity analysis, testing, correctness, ethical evaluation, and documentation in a computer science capstone.
A practical guide to integrating problem definition, data representation, modular programming, algorithms, complexity analysis, testing, correctness, and ethical evaluation into a responsible computer science capstone.
This quiz covers process management, context switching and scheduling, multitasking, traps and interrupts, and RISC-V privilege transitions.