Data Structures & Algorithmic Complexity

Technical screening rounds evaluate memory allocation, time complexity analysis, and pointer manipulation without executing code.

Exam Frequency: 5 to 10 questions in TCS Digital/Prime, Infosys SP, and Product rounds

Essential Formulas & Shortcut Rules

Binary Search: Time = O(log N), Space = O(1)

Optimal search in a sorted array.

QuickSort: Average = O(N log N), Worst-case = O(N²)

Occurs with poor pivot selection in already sorted data.

Balanced BST Height = ⌊log₂ N⌋

Ensures O(log N) lookup, insertion, and deletion.

Example 1: What is the time complexity of the following code snippet? for (int i = 1; i <= n; i *= 2) { for (int j = 0; j < n; j++) { sum += 1; } }

Step-by-Step Mathematical Derivation:

•Analyze outer loop: i starts at 1 and doubles each iteration (1, 2, 4, 8 ... n). The outer loop executes log₂ n times.

•Analyze inner loop: j runs from 0 to n - 1, executing exactly n times regardless of i.

•Total executions = (Number of outer iterations) × (Number of inner iterations) = (log₂ n) × n = O(n log n).

Answer: O(n log n)

💡 Speed Shortcut: Whenever a loop variable is multiplied or divided by a constant factor, its complexity is logarithmic (O(log n)).

✕Confusing O(N log N) with O(N²).
✕Assuming HashMaps guarantee O(1) in the worst-case (heavy collisions degrade to O(N) or O(log N) in Java 8 tree bins).

Instant Explanations • Timed

Assessment Simulator

2 Questions • No negative marking

15:00

1Data Structures & Algorithmic Complexity

medium

python

def mystery(n):
    count = 0
    i = 1
    while i < n:
        count += 1
        i *= 2
    return count

print(mystery(32))

What will be the output printed by executing the Python program shown above?

0 / 2 Answered

Answered (0)

Marked for Review (0)

Unvisited (2)