Timedora
Free Practice Quiz Question List

01 Algorithm Analysis and Big-O Notation Online Quiz Questions

Use this free practice quiz with 20 questions to review 01 Algorithm Analysis and Big-O Notation, test your knowledge, and prepare for your next test or exam.

20 questions
01
Choose one
1 point

Which statement best describes an abstract data type (ADT)?

  1. A

    An ADT specifies the exact memory layout used by a data structure.

  2. B

    An ADT specifies supported values and operations independently of implementation.

  3. C

    An ADT guarantees that every operation has constant running time.

  4. D

    An ADT is a proof that an algorithm terminates.

02
Choose all
1 point

Which three proof obligations are essential parts of a loop-invariant argument? Select all correct choices.

  1. A

    Initialization

  2. B

    Randomized testing

  3. C

    Maintenance

  4. D

    Termination

03
True or false
1 point

True or false: The input-size variable nn always means the number of elements in an array, regardless of the problem being analyzed.

  1. A

    True

  2. B

    False

04
Choose one
1 point

A stack uses which access discipline?

  1. A

    FIFO

  2. B

    LIFO

  3. C

    Priority order

  4. D

    Sorted order

05
Fill in the blank
1 point

In a correctness argument, the states what must be true before execution, and the states what is guaranteed after execution.

06
Choose all
1 point

Which two statements correctly compare worst-case and average-case analysis? Select all correct choices.

  1. A

    Worst-case analysis provides a guarantee for every input of a given size.

  2. B

    Average-case analysis is meaningful without any probability distribution.

  3. C

    Worst-case analysis always gives the exact elapsed time in seconds.

  4. D

    Average-case analysis uses an expected cost under a specified distribution.

07
Fill in the blank
1 point

Big-O gives an asymptotic , Big-Omega gives an asymptotic , and Big-Theta gives an asymptotically .

08
True or false
1 point

True or false: Binary search has logarithmic running time on any collection, even if the collection is unsorted or does not support efficient access to its middle element.

  1. A

    True

  2. B

    False

09
Open ended
1 point

Analyze a merge-sort-style algorithm that recursively sorts two subarrays of size n/2 and then merges the results in linear time. Write its recurrence and give a tight asymptotic bound for its running time.

10
Choose one
1 point

A program executes one loop taking Θ(n) time followed by a separate loop taking Θ(n²) time. What is the total asymptotic running time?

  1. A

    Θ(n)

  2. B

    Θ(n²)

  3. C

    Θ(n³)

  4. D

    Θ(log n)

11
Choose one
1 point

Which statement best distinguishes an abstract data type from its implementation?

  1. A

    An ADT specifies internal memory layout, while an implementation specifies only the allowed operations.

  2. B

    An ADT specifies supported values and operations, while an implementation specifies how those operations are realized.

  3. C

    An ADT guarantees a particular asymptotic complexity, while an implementation guarantees correctness.

  4. D

    An ADT is used only for recursive algorithms, while an implementation is used only for iterative algorithms.

12
True or false
1 point

True or false: If an algorithm runs in Θ(n)\Theta(n), then it is also technically O(n2)O(n^2).

  1. A

    True

  2. B

    False

13
Written response
1 point

What term names a condition that must remain true about a data structure's internal state throughout its operations?

14
Choose one
1 point

Consider the loop: set i=1i=1; while i<ni<n, perform constant-time work and set i=2ii=2i. What is its tight running time?

  1. A

    Θ(n)\Theta(n)

  2. B

    Θ(log⁡n)\Theta(\log n)

  3. C

    Θ(n2)\Theta(n^2)

  4. D

    Θ(1)\Theta(1)

15
Choose one
1 point

An outer loop runs for i=1i=1 through nn, and on iteration ii an inner loop performs constant-time work exactly ii times. What is the tight running time?

  1. A

    Θ(n)\Theta(n)

  2. B

    Θ(n2)\Theta(n^2)

  3. C

    Θ(nlog⁡n)\Theta(n\log n)

  4. D

    Θ(2n)\Theta(2^n)

16
Choose one
1 point

Which complexity statement correctly describes hash-table lookup under the conditions discussed in the material?

  1. A

    It is always Θ(1)\Theta(1), regardless of collisions.

  2. B

    It is always Θ(log⁡n)\Theta(\log n), because hashing keeps keys ordered.

  3. C

    It is O(1)O(1) on average but can be O(n)O(n) in the worst case.

  4. D

    It is O(nlog⁡n)O(n\log n) on average because every key must be sorted.

17
Written response
1 point

A recursive search has running time T(n)=T(n/2)+Θ(1)T(n)=T(n/2)+\Theta(1). What is its tight asymptotic running time?

18
Choose one
1 point

What auxiliary stack-space bounds can a recursive traversal have for a balanced binary tree versus a highly unbalanced binary tree, each containing nn nodes?

  1. A

    Both cases use Θ(1)\Theta(1) stack space because each node is processed once.

  2. B

    A balanced tree uses O(log⁡n)O(\log n) stack space, while a highly unbalanced tree can use O(n)O(n).

  3. C

    A balanced tree uses O(n)O(n) stack space, while a highly unbalanced tree uses O(log⁡n)O(\log n).

  4. D

    Both cases use O(nlog⁡n)O(n\log n) stack space because traversal visits all nodes.

19
Written response
1 point

A data structure has occasional expensive operations, but the average cost per operation over a long sequence remains small. What standard analysis term describes this average cost over the sequence?

20
Written response
1 point

An algorithm receives an input array and creates one temporary auxiliary array containing 100 elements. Each temporary element occupies 8 bytes. Ignoring any constant-size variables, how many bytes of auxiliary space does the temporary array require?