What is an algorithm?
An algorithm is a finite, precisely defined sequence of steps for solving a problem.
Study 1 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, precisely defined sequence of steps for solving a problem.
How do an ADT and data structure differ?
An ADT specifies values and permitted operations without describing implementation; a data structure is the concrete representation that implements it.
What does input size n measure?
Input size is the measure of problem scale, such as the number of array elements, string characters, graph vertices, or representation bits.
What is a cost model?
A cost model identifies which operations count as basic units of work, often treating arithmetic, assignment, comparison, and array access as constant-time.
What are the time and auxiliary space costs of summing an array?
The sum loop has runtime Θ(n) because it processes each element once, and auxiliary space Θ(1) because it uses only a fixed amount of extra memory.
What is the complexity of two nested n-iteration loops?
Two independent nested loops that each run n times perform Θ(n2) work because the iteration counts multiply.
What is auxiliary space?
Auxiliary space is memory used beyond the input; total space includes both the input storage and the algorithm’s additional memory.
What are sequential search’s best and worst cases?
For sequential search, the best case is Θ(1), while the worst case is Θ(n) when the target is last or absent.
What does Big-O notation express?
Big-O is an asymptotic upper bound: eventually, T(n)≤cf(n) for positive constants c and n0.
When is Θ(f(n)) appropriate?
Big-Θ is a tight asymptotic bound because the function is both an asymptotic upper bound and an asymptotic lower bound.
How is a runtime expression simplified asymptotically?
To simplify an asymptotic expression, remove constant multipliers and retain the fastest-growing term; thus 4n2+3n+9=Θ(n2).
Why is binary search Θ(logn)?
Binary search has runtime Θ(logn) because each step halves the remaining input, giving the recurrence T(n)=T(n/2)+Θ(1).
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 progressive guide to tree structure, binary-tree traversals, binary search tree operations, deletion, balancing, and the way tree height determines time and space costs.
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.