Unit 1: Introduction - Subjective Questions

Elementary data structures organize data so that it can be stored, accessed, and modified efficiently.

• Array: Stores elements in contiguous memory locations. It supports indexed access in time, while insertion or deletion at an arbitrary position generally takes time.
• Linked list: Stores elements in nodes connected by links. Accessing an arbitrary element takes time, but insertion or deletion at a known node can take time.
• Stack: A linear structure following Last In, First Out (LIFO). Its main operations are push, pop, and peek, typically performed in time.
• Queue: A linear structure following First In, First Out (FIFO). Its main operations are enqueue, dequeue, and front, typically performed in time with a suitable implementation.

The choice of data structure influences both the design and time complexity of an algorithm.

Arrays and linked lists differ as follows:

Arrays are preferable when frequent indexed access is needed. Linked lists are useful when frequent insertions and deletions occur and the relevant node is already known.

A stack follows the LIFO principle: the most recently inserted element is removed first.

• Operations: push, pop, and peek
• Typical operation cost:
• Applications:
  • Managing recursive function calls
  • Expression evaluation and parenthesis matching

A queue follows the FIFO principle: the earliest inserted element is removed first.

• Operations: enqueue, dequeue, and front
• Typical operation cost: when implemented using a linked list or circular array
• Applications:
  • Breadth-first search
  • Process scheduling and request handling

The ordering policies of these structures make them suitable for different algorithmic tasks.

A tree is a hierarchical structure consisting of nodes and edges. In a rooted tree, one node is the root, every non-root node has exactly one parent, and there is a unique path from the root to each node.

A graph consists of a set of vertices and a set of edges connecting pairs of vertices. Graphs may be directed or undirected and may contain cycles.

Major differences:

• A tree with nodes has exactly edges; a graph may have different numbers of edges.
• A tree is connected and has no cycles; a general graph may be disconnected or cyclic.
• Trees represent hierarchical relationships, while graphs represent arbitrary relationships.
• Both may be represented using adjacency-based structures, although trees also commonly use child or parent links.

Examples include file systems for trees and road networks for graphs.

A computational model is an abstract framework used to describe how algorithms execute and to estimate their resource usage.

The Random Access Machine (RAM) model represents a computer with a processor and an unbounded sequence of memory locations.

Common assumptions:

• Each memory location can be accessed directly.
• Basic arithmetic, assignment, comparison, and memory-access operations take constant time, usually .
• Instructions are executed sequentially unless control flow changes the order.
• Word-sized values fit in one memory cell.
• The running time is estimated by counting primitive operations.

The model simplifies real hardware behavior. It generally ignores factors such as cache misses, parallel execution, and differences between operation costs, but it enables machine-independent algorithm analysis.

In the RAM model, operations such as arithmetic, assignment, comparison, and direct memory access are generally treated as constant-time operations.

In the comparison model, an algorithm gains information about keys only by comparing pairs of keys. The primary cost is therefore the number of comparisons.

Comparison:

• The RAM model supports a broad set of primitive operations.
• The comparison model restricts how information about key order is obtained.
• Comparison sorting has a worst-case lower bound of comparisons.
• Under a richer RAM model, algorithms such as counting sort can run in time by using key values directly.

Thus, a complexity claim is meaningful only with respect to its computational model. An operation considered primitive in one model may require several steps or may not be available in another.

The input size, usually denoted by , measures the amount of data processed by an algorithm. Its meaning depends on the problem—for example, the number of array elements, vertices, digits, or bits.

To analyze an algorithm:

1. Identify the relevant input-size parameter.
2. Select an elementary operation, such as a comparison or assignment.
3. Count how many times that operation executes as a function of .
4. Form a running-time expression such as .
5. Retain the dominant growth term for asymptotic analysis, giving .

Operation counting gives a machine-independent approximation of running time. It is important to state the input measure clearly, especially for numeric algorithms, where the value of a number and the number of bits required to represent it are different.

For all inputs of size :

• Best-case complexity is the minimum resource usage:
• Worst-case complexity is the maximum resource usage:
• Average-case complexity is the expected resource usage under a specified input distribution:

The best case provides an optimistic bound, while the worst case provides a guaranteed upper limit. Average-case analysis may better represent typical performance, but it requires valid probability assumptions about the inputs. These three measures can have different asymptotic growth rates for the same algorithm.

Linear search compares the target with array elements from left to right until it finds a match or reaches the end.

• Best case: The target is the first element. Only one comparison is required, so .
• Worst case: The target is absent or appears in the last position. The algorithm performs comparisons, so .
• Average case: If the target is present and equally likely to occur at any position, the expected comparisons are
  
  Therefore, .

If unsuccessful searches are also possible, the exact expectation depends on their probability, but the average asymptotic complexity normally remains .

Asymptotic notations describe function growth for sufficiently large input sizes.

• Big O: means that is an asymptotic upper bound for .
• Big Omega: means that is an asymptotic lower bound for .
• Big Theta: means that is both an asymptotic upper and lower bound for .

Their relationship is

For example, belongs to , , and therefore . Big Theta gives a tight asymptotic bound, whereas Big O or Big Omega alone may not be tight.

Formal definition: A function is in if there exist positive constants and such that

for every .

Let and . For :

Therefore,

Choosing and satisfies the definition. Hence,

The constants are not unique; any sufficiently large with a suitable would also prove the result.

The increasing asymptotic order is

Justification:

• A constant does not grow with .
• Logarithmic growth is slower than every positive polynomial power.
• Linear growth is slower than linearithmic growth because grows without bound.
• is slower than because .
• Exponential growth eventually exceeds every fixed-degree polynomial.
• Factorial growth eventually exceeds fixed-base exponential growth because multiplies an increasing sequence of factors.

The logarithm base does not affect the asymptotic class because logarithms with different constant bases differ only by a constant factor.

Asymptotic analysis focuses on how resource usage grows as becomes large.

• Constant multiplicative factors usually depend on implementation or hardware and do not change the growth class.
• Lower-order terms become insignificant relative to the dominant term.
• This abstraction enables comparison across machines and programming languages.

For

the dominant term is . Removing the constant coefficient gives

Indeed,

a positive finite constant. This confirms that the function grows asymptotically like . Constants may still matter in practice for small or moderate inputs, even though they are omitted asymptotically.

Recursion is a technique in which a function solves a problem by calling itself on a smaller instance of that problem.

A recursive definition requires:

• Base case: A directly solvable case that stops further calls.
• Recursive case: A rule that reduces the problem toward the base case.

For factorial:

A corresponding algorithm returns when ; otherwise, it returns multiplied by the result for .

Each call reduces by one, so the process eventually reaches the base case. Without a valid base case or decreasing progress measure, recursion may continue indefinitely and cause a stack overflow.

Both approaches can compute factorial in time.

Recursive approach:

• Expresses factorial directly as .
• Often produces concise and mathematically natural code.
• Creates one call-stack frame per level.
• Uses auxiliary stack space.

Iterative approach:

• Starts with an accumulator and multiplies it by each integer from to .
• Uses a loop rather than repeated function calls.
• Uses auxiliary space.
• Usually avoids function-call overhead.

Thus, both versions have the recurrence or loop count corresponding to multiplication steps, but the iterative version is more space-efficient. Recursion can still be preferable for naturally recursive structures and divide-and-conquer algorithms because it may improve clarity and correctness.

A recurrence relation defines a function, such as running time, using its values on smaller inputs.

To construct a running-time recurrence:

1. Identify the input size .
2. Determine the number of recursive calls.
3. Determine the input size passed to each recursive call.
4. Calculate the non-recursive work performed by the current call.
5. Specify the base-case cost.

If an algorithm creates subproblems of size and performs additional work, its recurrence is commonly

with a base condition such as .

For example, binary search makes one recursive call on half of the input and performs constant extra work, giving

Repeated expansion gives


and after continuing to the base case,

Using

we obtain

Therefore,

The quadratic term dominates, so

This recurrence can describe a recursive algorithm that reduces the input by one at each level while performing linear work in the current input size.

Binary search compares the target with the middle element and then searches at most one half of the remaining array.

For an input of size :

• There is one recursive subproblem of size approximately .
• Finding the middle index and comparing the key require work.

Thus,

with .

After expansions,

The base case is reached when

so . Therefore,

This is the worst-case running time. The best case is when the target is found in the first comparison.

Merge sort divides an input into two halves, recursively sorts each half, and merges them in linear time. Its recurrence is

with .

In the recursion tree:

• Level costs .
• Level contains two problems of size , costing .
• At any level , there are problems of size , so the total level cost is .
• The tree has non-leaf levels.
• There are leaves, whose total cost is .

Hence,

and therefore

The result assumes that is a power of two; floors and ceilings do not change the asymptotic bound.

For

compare with .

• Case 1: If for some , then .
• Case 2: If , then .
• Case 3: If and the regularity condition holds, then .

Applications:

• (a) , , so . Since is polynomially smaller, Case 1 gives .
• (b) , , so . Since , Case 2 gives .
• (c) , , while is polynomially larger than . The regularity condition holds because . Case 3 gives .

The standard theorem does not directly apply to every recurrence, especially those with unequal subproblem sizes.