Unit 1: Behaviour Analysis - Practice Quiz

1 What does the limit of a function describe?

2 In algorithm analysis, what does asymptotic behavior mainly describe?

3 Which notation commonly represents an upper bound on an algorithm's growth rate?

4 What happens to the importance of constant operations as input size grows?

5 What does worst-case analysis measure?

6 Which complexity class generally grows more slowly?

7 What is the worst-case time complexity of accessing an element by index in an array?

8 Which notation represents a tight asymptotic bound?

9 What is the worst-case time complexity of a linear search in an unsorted array?

10 What does the effectiveness of an algorithm mainly refer to?

11 What does the efficiency of an algorithm mainly measure?

12 Two algorithms solve the same problem correctly. Which one is generally more efficient?

13 Why are algorithms analyzed before implementation?

14 Which factor is most important when comparing algorithm efficiency for large inputs?

15 What does time complexity measure?

16 What does space complexity measure?

17 What is the time complexity of a loop that runs exactly times?

18 What is the time complexity of two separate nested loops, each running times?

19 What is an algorithmic trade-off?

20 What does a time-space trade-off usually mean?

21 For and , what does imply?

22 An algorithm repeatedly replaces by until . Which expression best describes the number of repetitions?

23 Suppose and . What is ?

24 A condition is evaluated as x != 0 && 100 / x > 5 using short-circuit logic. What happens when ?

25 Which statement correctly interprets a worst-case bound of for an algorithm?

26 Insertion sort is applied to an array of distinct values. Which input arrangement produces its worst-case running time?

27 An algorithm has worst-case complexity and best-case complexity . Which claim is valid for all inputs of size ?

28 Binary search is performed on a sorted array of elements. What is the maximum number of element comparisons under the standard midpoint implementation?

29 Algorithm A takes operations, while Algorithm B takes operations. Ignoring machine effects, for which listed input size is Algorithm A more efficient?

30 Two sorting algorithms have the same time complexity, but Algorithm X performs fewer comparisons and uses the same memory as Algorithm Y. What is the most justified conclusion?

31 An algorithm runs quickly but sometimes returns an incorrect result. How should it be evaluated?

32 Algorithm P requires operations, while Algorithm Q requires operations. Which algorithm is generally more scalable for sufficiently large ?

33 What is the time complexity of the following loop?

for i = 1 to n:

for j = 1 to i:

perform_constant_work()

34 An algorithm first executes a loop and then executes a separate loop. What is its total time complexity?

35 A recursive function makes one call on input size and stores a constant amount of local data per call. What is its auxiliary space complexity if recursion reaches ?

36 A loop starts with and updates after each iteration until . What is its time complexity?

37 A recursive solution recalculates the same subproblems many times. Memoization is added. What trade-off is being made?

38 A program replaces repeated linear searches in a list with lookups in a hash table. What is the primary expected trade-off?

39 A large file is compressed before being sent through a slow network. Under which condition is compression most likely to reduce the total completion time?

40 A stable merge sort and an in-place heap sort both take time. Which requirement most strongly favors heap sort?

41 Let and be positive functions for sufficiently large . Which statement about the limit is correct?

42 Suppose and . Which asymptotic conclusion is valid?

43 For positive functions and , assume . Which conclusion follows directly?

44 Let for sufficiently large . How does compare asymptotically with ?

45 An algorithm's worst-case running time is known to satisfy and . What is the strongest justified classification?

46 A deterministic quicksort implementation always chooses the first array element as its pivot. Which statement correctly characterizes its worst case on arrays of distinct keys?

47 A dynamic program runs in time, where is a positive integer supplied in binary. Which interpretation is most accurate?

48 For every input of size , an algorithm executes exactly one of two feasible branches. Their tight worst-case costs are and . What is the overall tight worst-case cost?

49 Algorithm A uses primitive operations, while Algorithm B uses operations. Both are correct. What can be concluded about their practical running times for inputs up to a fixed limit ?

50 A procedure returns a correct answer whenever it terminates, but on some valid inputs it loops forever. Which property does it possess?

51 A Las Vegas randomized algorithm always returns the correct result and has expected running time , but it may repeatedly restart. Which claim is justified?

52 An algorithm reports all intersections among geometric objects in time. Why can this be more informative than a bound expressed only in ?

53 Consider a loop where, for each integer from through , an inner counter takes the values while it is less than . What is the total running time?

54 What is the tight asymptotic solution of with constant base cases?

55 A depth-first divide-and-conquer algorithm splits a problem into two halves. Each active call allocates an auxiliary array proportional to its subproblem size and keeps it until that call returns. What is the peak auxiliary space?

56 A dynamic array triples its capacity whenever full. Copying an array of capacity costs . Starting empty, what is the total copying cost of the first append operations?

57 A naive recursive solver for a problem with state repeatedly recomputes states and takes exponential time. There are reachable states, each requiring transition work. What trade-off does full memoization provide?

58 Compared with storing all keys exactly in a hash set, which guarantee describes a standard Bloom filter with no deletions?

59 For exact subset sum on unrestricted integers, a meet-in-the-middle method stores all sums from each half. What time-space profile does it typically achieve?

60 A data structure can precompute a table in time and space, after which each query costs . Without the table, each query costs and preprocessing is constant. For queries, when is precomputation asymptotically faster?