Unit 1: Analysis of Algorithms and Divide-and-Conquer - Subjective Questions

Time complexity measures the number of basic operations performed by an algorithm as a function of the input size . It describes how the running time grows when increases.

Space complexity measures the total memory required by an algorithm as a function of . It consists of:

• Input space: Memory required to store the input.
• Auxiliary space: Additional memory used by the algorithm, such as temporary variables, arrays, and recursion stacks.

For example, an algorithm that scans an array once has time complexity . If it uses only a fixed number of variables, its auxiliary space complexity is .

Complexities are expressed in terms of input size because actual running time and memory usage depend on the computer, programming language, and implementation. Growth-rate analysis provides a machine-independent way to compare algorithms.

Asymptotic notations describe the growth rate of an algorithm for sufficiently large input sizes.

• Big-O notation: if there exist constants and such that
  
  It gives an asymptotic upper bound.

• Big-Omega notation: if there exist constants and such that
  
  It gives an asymptotic lower bound.

• Big-Theta notation: if there exist positive constants , , and such that
  
  It gives a tight bound.

For example, , , and therefore .

Insertion Sort builds a sorted prefix by inserting each element into its correct position.

Best case: The array is already sorted. Each element requires only one comparison and no shifting.

Worst case: The array is in reverse order. During iteration , the key is compared with and shifted past all preceding elements.

Average case: On average, approximately half of the sorted prefix is examined and shifted for each insertion.

Therefore:

• Best-case time:
• Average-case time:
• Worst-case time:
• Auxiliary space:

Insertion Sort is in-place, stable, and efficient for small or nearly sorted inputs.

Merge Sort divides an array into two halves, recursively sorts both halves, and merges the sorted halves.

For an input of size , the recurrence is

with base case .

At recursion level :

• There are subproblems.
• Each subproblem has size .
• The total merging work is .

The recursion has levels, so

This bound applies to the best, average, and worst cases because Merge Sort performs essentially the same divisions and merges regardless of input order.

Space complexity:

• Temporary arrays used during merging require auxiliary space.
• The recursion stack requires space.
• Thus, the standard array-based implementation has total auxiliary space .

Merge Sort is stable but is generally not in-place for arrays.

Suitable applications:

• Insertion Sort is suitable for small arrays, nearly sorted data, and environments with limited memory.
• Merge Sort is suitable for large data sets, linked lists, external sorting, and applications requiring predictable performance.
• Hybrid sorting algorithms often use Merge Sort for large subarrays and Insertion Sort for small subarrays.

A systematic analysis of an iterative algorithm involves the following steps:

1. Identify the input size .
2. Select the basic operation to count.
3. Determine how many times each loop executes.
4. Express the count as a summation or equation.
5. Simplify it and retain the dominant growth term.

Consider the loop:

i = 1
while i <= n:
    perform constant-time work
    i = 2 * i

After iterations, the value of is . The loop stops when . Therefore,

If each iteration performs work, then

A multiplicative change in the loop variable usually produces logarithmic complexity, whereas an additive change usually produces linear complexity.

For a fixed value of , the inner loop takes the values

Therefore, it executes times.

The total number of executions is

For an upper bound, , so

For a lower bound, consider from to . There are approximately such values, and each contributes at least iterations. Hence,

Combining both bounds gives

The analysis demonstrates that nested loops are not automatically quadratic; the inner loop's progression must be examined carefully.

A recurrence relation expresses the running time of a recursive algorithm in terms of the running time on smaller inputs. It generally includes:

• The number of recursive calls.
• The size of each recursive subproblem.
• The non-recursive work performed in the current call.
• A base-case cost.

Binary search examines the middle element and recursively searches one half of the array. Its recurrence is

with .

After substitutions,

The base case is reached when

so . Therefore,

The recursion stack also has depth , so a recursive implementation uses auxiliary stack space.

Assume is a power of and .

Upper bound: Guess that

Assuming the bound holds for ,

Thus,

For ,

Therefore, .

Lower bound: Guess that

for a suitable constant . Using the inductive hypothesis,

Hence,

For , this is at least . Therefore, .

Since both bounds hold,

Repeated substitution gives

Substituting for ,

After substitutions,

Setting reaches the base case:

Using the arithmetic-series formula,

we obtain

Such a recurrence occurs when an algorithm recursively solves a problem of size and performs additional work at each call. For example, a recursive sorting procedure that places one element correctly and scans all remaining elements at every level may have this recurrence.

The root represents a problem of size and contributes non-recursive cost .

At level , there are subproblems of size . Their total non-recursive cost is

At level , there are subproblems, each of size . The level cost is

The recursion ends when the subproblem size becomes :

Thus, there are internal levels, each costing . Their total cost is

At the leaf level there are leaves. If each leaf costs , the total leaf cost is .

Therefore,

The recursion tree makes it clear that equal work is performed at every internal level.

For

where and , compare with the critical function

Case 1: Recursive work dominates

If

for some , then

Case 2: Balanced work

If

for some , then

Case 3: Non-recursive work dominates

If

for some , and the regularity condition

holds for some constant , then

The polynomial-gap and regularity conditions are important when deciding whether a case applies.

(a)

Here , , and

Since , Case 1 applies:

(b)

Here , , and

Since , Case 2 applies with :

(c)

Here the critical function is , while . The regularity condition holds because

for . Therefore, Case 3 applies:

These examples illustrate all three cases of the Master Method.

The Master Method is designed primarily for recurrences of the form

where the recursive subproblems have equal size.

It cannot be directly applied in the following situations:

• Unequal subproblem sizes:
  
• Changing number of subproblems:
  
• Subproblem size not reduced by a constant factor:
  
• Certain functions without the required polynomial gap:
  
  is not covered by the basic three-case statement.
• Failure of the regularity condition in Case 3.

Such recurrences may require substitution, a recursion tree, iteration, the Akra-Bazzi method, or another specialized technique.

Divide-and-conquer solves a problem by breaking it into smaller subproblems of the same general form.

Its three phases are:

1. Divide: Split a problem of size into smaller subproblems.
2. Conquer: Solve the subproblems recursively. Small subproblems are solved directly as base cases.
3. Combine: Combine the subproblem solutions to obtain the solution to the original problem.

If an algorithm creates subproblems, each of size , and requires work for division and combination, its recurrence is

Examples include:

• Merge Sort:
• Binary Search:
• Strassen's algorithm:

The strategy is especially useful when subproblems are independent and substantially smaller than the original problem.

Let two matrices be divided into quadrants:

Strassen's algorithm computes seven products instead of the eight products used by conventional block multiplication:

The result quadrants are

The recurrence is

By the Master Method,

This is asymptotically faster than conventional matrix multiplication, which takes time. However, additional additions, memory usage, numerical stability concerns, and large constant factors make Strassen's algorithm most useful for sufficiently large matrices.

For a set of elements arranged in nondecreasing order as

the element is called the -th order statistic.

Important order statistics include:

• Minimum:
• Maximum:
• -th smallest:
• -th largest:
• Median: for odd ; for even , a convention may use either middle element or their average.

Sorting-based approach:

• Sort the entire collection and access position .
• Time complexity is generally .
• It is useful when many order-statistic queries must be answered.

Selection-based approach:

• Quick Select finds one desired order statistic without fully sorting the data.
• Its expected time is .
• Deterministic median-of-medians selection guarantees worst-case time.

Thus, selection is usually preferable for a single order-statistic query.

Quick Select is based on the partition operation used in Quick Sort.

Algorithm:

1. Select a pivot.
2. Partition the array so that elements smaller than the pivot precede it and larger elements follow it.
3. Let the pivot's sorted rank be .
4. If , return the pivot.
5. If , recursively select from the left partition.
6. If , recursively select from the right partition with adjusted rank .

For , suppose the pivot is . A valid partition is

The pivot has rank because exactly three elements are smaller than it. Since the requested value is the fourth smallest, equals the pivot's rank.

Therefore, the answer is

Quick Select recursively processes only one partition rather than both. It may be implemented in-place and typically uses partitioning space, excluding the recursion stack.

Quick Select partitions the input in time and then recursively processes only the partition containing the desired order statistic.

Balanced or best case: If each pivot divides the array approximately in half,

Expanding the recurrence gives

Expected case: With a random pivot, the partitions are sufficiently balanced on average. The expected running time is

Worst case: If the pivot is repeatedly the smallest or largest element, the recursive problem has size :

This can occur with poor deterministic pivot choices on specially ordered input.

Randomized pivot selection:

• Selects the pivot uniformly at random.
• Makes consistently bad partitions highly unlikely.
• Prevents fixed input arrangements from reliably forcing worst-case behavior.
• Gives expected time for every fixed input.

The worst-case bound remains , but its occurrence becomes probabilistically unlikely.

In an array of elements, the -th largest element is the element with ascending rank

Therefore, a -th smallest selection algorithm can find the -th largest by searching for order statistic .

For example, in

. The second largest element has ascending rank

The fifth smallest element is , so the second largest is .

Quick Select:

• Expected time:
• Worst-case time:
• Usually in-place
• Suitable for a single selection query

Min-heap of size :

• Time:
• Space:
• Useful for streaming data or when all elements cannot be rearranged

Max-heap containing all elements:

• Heap construction:
• Extracting the maximum times:
• Space:

Thus, Quick Select is generally fastest in expectation for an in-memory single query, while a size- heap is useful for streams and limited-storage processing.