GATE 2027 - ALGORITHM 04 | Analysis of Algorithm - Loop Complexities and Space Complexity | CSE & DA

Main Ideas

Recursive Algorithm Analysis

A common process for analyzing recursive code is to derive a recurrence from the code, solve it, apply the base condition, and identify the dominant term.

A flowchart example compares best- and worst-case behavior by counting recursive calls along possible paths. Fewer calls mean less work; more calls mean more work.

• Best case: (T(n) = 2T(n/2) + a), which solves to (\Theta(n)).
• Worst case: The recurrence is transcribed as (T(n) = 8T(n/2) + a). The instructor says this is (\Theta(n)), but that conclusion is inconsistent with the recurrence as written: (8T(n/2) + a) solves to (\Theta(n^3)). The subtitles may have misrepresented the recurrence or the calculation.

Analyzing a Loop’s Time Complexity

To find a loop’s complexity, consider both:

1. How many times the loop executes.
2. The cost of the statements inside the loop body.

A loop that runs (n) times is not necessarily (\Theta(n)) overall if its body has a nonconstant cost. For example, (n) iterations with a (\Theta(n)) body take (\Theta(n^2)) time.

Examples discussed include:

• Repeating a constant-time operation (n) times takes (\Theta(n)).
• A loop that breaks on its first iteration takes (\Theta(1)), even if its stated limit is (n).
• A loop that adds (i) to an accumulator for (i = 1, \ldots, n) computes a sum of (n(n+1)/2) and takes (\Theta(n)) time.
• A divisibility check starting at (i = 1) stops immediately because 1 divides every positive integer, so it takes (\Theta(1)). Starting at (i = 2) changes the analysis: the best case can be (\Theta(1)), while a prime input greater than (n) can lead to (\Theta(n)) iterations.
• If a loop calls a function on each iteration, include the function’s cost. For example, (n) calls to a function costing (f(n)) give an overall cost of (\Theta(nf(n))).

Common Loop-Update Patterns

The loop variable’s update pattern helps determine how many iterations the loop performs:

• Adding a fixed positive constant (b): The loop runs about (n/b) times, which is (\Theta(n)) when (b) is constant.
• Multiplying by a constant (b > 1): The loop runs about (\log_b n) times, giving a complexity of (\Theta(\log n)). The same reasoning applies to equivalent for and while loops.
• Assignment in a condition: An assignment used where a condition is expected can remain true indefinitely, resulting in an infinite loop.

Nested and Mutually Exclusive Loops

Loop structures can be broadly divided into nested loops and sequential or mutually exclusive loops.

• Nested independent loops: If the inner loop’s bounds do not depend on the outer loop, find each loop’s cost and multiply them. Two loops that each run (\Theta(n)) times take (\Theta(n^2)). An example with (n) outer iterations and roughly (n/2) inner iterations performs about (5n^2/2) additions to an accumulator, giving an overall runtime of (\Theta(n^2)).
• Nested dependent loops: If the inner loop’s behavior depends on the outer loop’s value, analyze its iteration count in relation to the outer loop.
• Sequential or mutually exclusive loops: Add the costs rather than multiply them. Sections costing (\Theta(n)) and (\Theta(m)) together take (\Theta(n + m)). Likewise, sections costing (\Theta(n)), (\Theta(n)), and (\Theta(n^2)) combine to (\Theta(n^2)), since the dominant term determines the order.

Space Complexity

The lesson focuses on auxiliary space, which excludes the input supplied to the algorithm.

• A linear-search algorithm uses only a constant number of extra variables, so its auxiliary space is (\Theta(1)).
• An iterative array-summing algorithm also uses only a constant number of extra variables, so it uses (\Theta(1)) auxiliary space.
• A recursive version creates a recursion stack. If its recursion depth is proportional to (n), the stack requires (\Theta(n)) space.

The key lesson is to count all memory created by the algorithm, including recursion-stack space—not just explicit arrays or variables.

Speakers and Sources

• Aditya Jain Sir — The instructor presenting the lesson. In the subtitles, he identifies himself as GATE Computer Science 2019 AIR 60 and says he completed a master’s degree at IIT Bombay.
• Live audience and chat participants — Students respond to questions, but their identities are not provided.