What does an algorithm specify?
A A processor's wiring
B Steps for solving a problem
C A database table
D A programming language name
Answer: B. Steps for solving a problem. An algorithm defines a finite procedure for transforming inputs into results.
What should a correct algorithm produce?
A Required result for valid input
B Random output every run
C Only a printed message
D A sorted list always
Answer: A. Required result for valid input. Correctness means the algorithm meets its specification for the intended inputs.
What does time complexity describe?
A Exact clock time
B Program file size
C Growth in operation count
D Processor temperature
Answer: C. Growth in operation count. Time complexity studies how an operation count scales with input size.
What does space complexity measure?
A Growth in memory use
B Number of source lines
C Network speed
D Compiler version
Answer: A. Growth in memory use. Space complexity tracks memory requirements as the input grows.
What does Big O usually express?
A Asymptotic upper bound
B Exact execution time
C Minimum memory address
D A loop's starting value
Answer: A. Asymptotic upper bound. Big O gives an asymptotic upper bound on growth.
What does Big Omega express?
A Asymptotic lower bound
B Exact running time
C Maximum input length
D Average source code size
Answer: A. Asymptotic lower bound. Big Omega describes an asymptotic lower bound.
What does Big Theta express?
A A strict upper bound only
B Tight asymptotic bound
C A random estimate
D Exact instruction count
Answer: B. Tight asymptotic bound. Theta bounds growth both above and below asymptotically.
What is worst case analysis?
A Minimum work for input size
B Work on sorted input only
C Expected work after randomization
D Maximum work for input size
Answer: D. Maximum work for input size. Worst case analysis bounds the most work for inputs of a given size.
What is best case analysis?
A Maximum work for input size
B Minimum work for input size
C Average memory use
D Work on every possible input
Answer: B. Minimum work for input size. Best case analysis studies the easiest input of a given size.
What does average case analysis require?
A A sorted input always
B A fixed processor clock
C A hash table only
D An input probability model
Answer: D. An input probability model. Average case results depend on assumptions about input distributions.
A single loop over n items is typically?
A O(n)
B O(1)
C O(log n)
D O(n squared)
Answer: A. O(n). A loop with constant work per item performs work proportional to n.
Two nested loops each over n items are typically?
A O(n squared)
B O(n)
C O(log n)
D O(1)
Answer: A. O(n squared). The inner loop runs about n times for each of n outer iterations.
Repeatedly halving n items takes how many levels?
A O(n)
B O(n squared)
C O(log n)
D O(1)
Answer: C. O(log n). Halving the remaining size reaches one after logarithmically many steps.
What prerequisite does binary search need?
A Sorted data
B Unique values
C A linked list
D Negative numbers
Answer: A. Sorted data. Binary search discards half the range based on sorted order.
What is linear search's key advantage?
A Always logarithmic time
B Requires a tree
C Finds duplicates in constant time
D Works without sorted order
Answer: D. Works without sorted order. Linear search can inspect an unsorted collection directly.
What is selection sort's typical time complexity?
A O(n log n)
B O(log n)
C O(n squared)
D O(1)
Answer: C. O(n squared). Selection sort repeatedly scans the remaining suffix for its minimum.
What is insertion sort's best case on sorted data?
A O(n squared)
B O(n)
C O(log n)
D O(n log n)
Answer: B. O(n). On already sorted input, insertion sort performs only a linear number of checks.
What is merge sort's typical time complexity?
A O(n squared)
B O(n log n)
C O(log n)
D O(1)
Answer: B. O(n log n). Merge sort divides the input and merges across logarithmically many levels.
What is quicksort's average time complexity?
A O(n squared)
B O(log n)
C O(1)
D O(n log n)
Answer: D. O(n log n). With reasonably balanced partitions, quicksort has expected n log n work.
What is quicksort's worst case time complexity?
A O(n log n)
B O(log n)
C O(1)
D O(n squared)
Answer: D. O(n squared). Repeatedly very unbalanced partitions produce quadratic work.
What does a stable sort preserve?
A Original array capacity
B The exact memory addresses
C Order of equal keyed items
D Input values without comparisons
Answer: C. Order of equal keyed items. A stable sort retains the original relative order of equal keys.
What does an in place algorithm usually limit?
A Input size
B Number of output values
C Number of comparisons always
D Extra auxiliary memory
Answer: D. Extra auxiliary memory. In place algorithms use little additional storage beyond the input representation.
What does quicksort partitioning do?
A Combines sorted halves
B Finds a graph path
C Groups items around a pivot
D Builds a hash function
Answer: C. Groups items around a pivot. Partitioning places items on either side of a chosen pivot according to comparison.
What does merge sort's merge step do?
A Chooses a graph root
B Hashes each element
C Combines sorted sequences
D Reverses every subarray
Answer: C. Combines sorted sequences. The merge step combines two sorted runs into one ordered sequence.
Why does a recursive algorithm need a base case?
A To increase its input
B To stop recursive calls
C To sort its function names
D To allocate a queue
Answer: B. To stop recursive calls. A base case handles the simplest instance without another recursive call.