DSA in 30 Days, Episode 1: Complexity, Arrays and Recursion with Tested Examples

Complexity tells you how the work of a program grows when the input grows. Arrays are the simplest place to see it, and recursion is where you will need it most. This is Episode 1 of the TechVani 30-day DSA series, and these are the notes for the Ep1 video.

Video for this lesson: the link will be added here when the video is uploaded.

This is a TechVani Proof Lab lesson: understand it, see it work, solve it yourself. Every count, address and trace below was run by a program. It is a general BTech CSE lesson, not an official syllabus.

1. What is an algorithm, and why count its work?

	Answer
What	A finite list of clear steps that turns an input into an output.
Why count	Two programs can give the same answer, but one may take 10 steps and the other 1,000,000. Counting steps lets you compare them without a stopwatch or a particular computer.
Where used	Choosing a search method, picking a data structure, and answering "is this solution fast enough?" in exams and interviews.
How	Count how many basic steps run as a function of the input size n.

2. Time and space

Time complexity is the number of steps as n grows. Space complexity measures memory as n grows. Here we report auxiliary space: extra storage apart from the input. Total space also includes the input. We counted real steps for three kinds of loops, for n = 10, 100 and 1,000:

Kind of work	n = 10	n = 100	n = 1,000
One loop over the items (linear)	10	100	1,000
Loop inside a loop (all pairs)	100	10,000	1,000,000
Binary search, worst case (checks)	4	7	10

Read it like this: when n grows 10 times, the linear count grows 10 times, the pairs count grows 100 times, and binary search adds only about 3 checks. A sorted array of 100 items needs at most 7 steps to search, which Episode 2 proves.

3. Big O rules

Big O keeps only the part that grows fastest and ignores constants. Five rules cover almost every question:

1. Drop constants. 5n becomes O(n).
2. Drop smaller terms. 3n² + 5n + 2 becomes O(n²). At n = 1,000 the full formula is 3.005002 times n², so the smaller terms barely matter.
3. Steps one after another add. A loop of n then a loop of n is O(n + n) = O(n).
4. Nested steps multiply. A loop of n inside a loop of n is O(n²).
5. Different inputs, different letters. A loop over a and a loop over b is O(a + b), not O(n).

Sequential: [n visits] -> [m visits] = n + m
Full nested: n rows x n columns = n^2
Triangular: 0 + 1 + ... + (n-1) = n(n-1)/2
Halving: n -> floor(n/2) -> ... -> 1 = logarithmic

Nested loops do not always mean n². Count the actual inner-loop range; a halving loop is logarithmic. Multiplication is safe for two independent full ranges.

4. The common classes

Illustrative growth values at n = 1,000 (and n = 20 for the last one), not exact operation counts for every implementation:

Class	Steps	Example
O(1)	1	read a[i] by index
O(log n)	10	binary search
O(n)	1,000	linear search, sum of a list
O(n log n)	9,966	n log2 n rounded: 9,965.784..., not a merge-sort comparison count
O(n²)	1,000,000	all pairs
O(2ⁿ) at n = 20	1,048,576	all subsets

5. Best, worst and average case

Take linear search for a value in a list of 10 items. We ran every target:

Case	Checks	When
Best	1	target is the first item
Worst	10	target is last (or missing)
Average	5.5	target equally likely at any place: (n + 1) / 2

Exams ask for worst case unless told otherwise. Case and bound are separate choices. O means an upper bound, Omega a lower bound, and Theta a tight bound for whichever case you chose. Worst-case linear search is Theta(n); best-case successful search is Theta(1). An O(n²) upper bound for linear search is true but loose. State the case rather than treating O as "worst" or Omega as "best".

Choice	Meaning	Linear-search example
Best case	Cheapest input of size n	1 check for a first-item hit
Worst case	Most expensive input of size n	n checks for last/missing
Average case	Expected cost under a stated distribution	(n+1)/2 for uniform successful positions
O / Omega / Theta	Upper / lower / tight growth bounds	Worst case Theta(n), best case Theta(1)

For an empty list, no comparisons run. The 5.5 average assumes a successful search equally likely at each of ten positions; adding missing searches changes the distribution and the average.

6. Space complexity

When reporting auxiliary space, count extra memory, not the input. State this convention explicitly. Adding up a list with one variable is O(1) space. Making a reversed copy of the list is O(n) space. Swapping elements inside the same list is "in place" and is O(1) extra space.

7. Arrays and the address formula

What: an array stores items of the same type side by side in memory. Why it is fast: because items are side by side, the computer finds item i with one calculation, so reading a[i] is O(1).

Address of a[i] = base + i x size (0-based index).
Example: base = 1000, each item 4 bytes, i = 99, so address = 1000 + 99 x 4 = 1396.

base 1000; item width 4 bytes
index:      0       1       2       3
address: 1000    1004    1008    1012
         [item0][item1][item2][item3]
index 99 -> 1000 + 99*4 = 1396

These address formulas model fixed-width, contiguous arrays such as C arrays. A Python list stores references, not same-type values laid out inline. Do not use the formula as an actual Python object address. For a lower index bound L, use base + (i - L) x size, where base is the address of a[L]. Access must stay within valid bounds.

8. Insert and delete in an array

Items must stay side by side, so inserting or deleting moves the items after the position. We counted the real moves on a list of 10:

Position	Moves to insert	Moves to delete
start	10	9
middle	5	4
end	0	0

Result: at the start every item moves, so insert and delete cost O(n). At the end nothing moves, so O(1) (when there is free space). Insert at index k moves n - k items.

Insert X at k=2; n=4 with a spare slot:
[A B C D _] -> [A B C C D] -> [A B X C D]
                    2 existing-item shifts
Delete k=2; n=5:
[A B X C D] -> [A B C D _]
                    2 existing-item shifts

Delete at index k shifts n - 1 - k existing items. The table counts shifts only, not the final inserted write or capacity growth. End insertion is O(1) if capacity is free; a dynamic-array append is amortized O(1), but an individual resize can take O(n).

9. Traversal and the Two Sum problem

Traversal means visiting each item once: O(n). Two Sum: find two items whose sum is the target. List [2, 7, 11, 15, 3, 6], target 9.

Brute force tries all pairs. It found the items at indexes (0, 1) after 1 checks. For 100 items there are 100 x 99 / 2 = 4,950 pairs, so it is O(n²). Better: remember the numbers already seen in a dictionary and look up target - x. One pass, expected O(n) time with expected O(1) dictionary operations, and O(n) auxiliary space. Adversarial hash collisions can make the worst-case time O(n²). It returned the same indexes (0, 1).

def two_sum(a, target):
    seen = {}
    for i, x in enumerate(a):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i
    return None

Trade-off: the fast version spends memory to save time. Exams like this answer: time O(n²) to expected O(n), auxiliary space O(1) to O(n).

Two Sum target 9, input [2,7,11,15,3,6]
i=0: x=2; need 7; absent -> seen {2:0}
i=1: x=7; need 2; found -> return (0,1)
Lookup BEFORE storing x avoids reusing its index.
[3,3], target 6 -> (0,1); [3], target 6 -> None

Method	Time model	Auxiliary space	When useful
Pair scan	Worst Theta(n²)	O(1)	Small input or little spare memory
Dictionary	Expected O(n); worst O(n²)	O(n)	Fast single pass with hash storage

10. Two-dimensional arrays

Memory is a line, so a 2D array is stored row by row (row-major, used by C) or column by column (column-major). Let the array have R rows and C columns.

Row-major: address of a[i][j] = base + (i x C + j) x size
Column-major: address of a[i][j] = base + (j x R + i) x size
Example: a 3 x 4 array, base 2000, size 2, find a[2][1]. Row-major: 2000 + (2 x 4 + 1) x 2 = 2018. Column-major: 2000 + (1 x 3 + 2) x 2 = 2010. Both were confirmed by laying out the cells in a program.

3 rows x 4 columns; cells labelled ij:
     col0 col1 col2 col3
row0  00   01   02   03
row1  10   11   12   13
row2  20  [21]  22   23
Row order: 00 01 02 03 10 11 12 13 20 [21] 22 23
Col order: 00 10 20 01 11 [21] 02 12 22 03 13 23
Cell 21 offset: row-major 9, column-major 5

The formulas assume 0-based indices. With row lower bound Lr and column lower bound Lc, replace i by i - Lr and j by j - Lc. R and C remain the dimension lengths. For example, row-major is base + ((i - Lr) x C + j - Lc) x size.

11. Recursion and recurrence relations

What: a function that calls itself on a smaller input. It needs a base case to stop. Why: some problems (trees, divide and conquer) are naturally "the same problem, smaller". How the computer does it: each call waits on the call stack until the smaller call returns.

fact(4) goes 4 calls deep: fact(4) → fact(3) → fact(2) → fact(1). It returns 24. Time T(n) = T(n-1) + 1, so O(n), and the stack also needs O(n) space.

The Fibonacci trap: naive fib(10) = 55 took 177 calls because it repeats work. Remembering results (memoization) cuts this to 19 function entries in the manual-cache implementation below, including cache hits. A cache decorator can report only 11 executed bodies instead; these are different counting conventions. With unit-cost arithmetic, memoization is O(n) time and O(n) auxiliary space. Large-integer arithmetic is not unit-cost when n grows.

Three recurrences you must know:

Recurrence	Result	Example	Checked (n = 1,024)
T(n) = T(n-1) + 1	O(n)	factorial, linear recursion	1,024 calls
T(n) = T(n/2) + 1	O(log n)	binary search	11 steps
T(n) = 2T(n/2) + n	O(n log n)	merge sort	11,264 = 1,024 x 10 + 1,024

Master theorem shortcut for T(n) = aT(n/b) + n^d: compare a with b^d. If a < b^d the answer is O(n^d). If equal, O(n^d log n). If a > b^d, O(n^{log_b a}). For merge sort a = 2, b = 2, d = 1, so a = b^d and the answer is O(n log n).

fact(4) waits for fact(3)
  fact(3) waits for fact(2)
    fact(2) waits for fact(1)
      fact(1) returns 1  <- base case
    return 2*1 = 2
  return 3*2 = 6
return 4*6 = 24

fib(5) branches to fib(4) and fib(3)
fib(4) branches to fib(3) and fib(2)
                       ^ repeated subproblem

The recurrence table uses T(1) = 1 and powers of two for halving. Its merge-sort row models one unit per element at each merge level plus one unit at each leaf, not an exact comparison count. For n = 1,024 there are ten merge levels of 1,024 units plus 1,024 leaf units. Factorial counts use the base case fact(1); allowing fact(0) gives a different entry count.

The Master shortcut here requires fixed a >= 1, b > 1, d >= 0 and a nonrecursive term Theta(n^d). Floors/ceilings do not change these asymptotic bounds. It does not apply to T(n) = T(n-1) + 1. A recursive call that fails to move toward the base case may never terminate.

Run the proof lab

Python 3, standard library only. Counts are logical loop visits, array shifts, search probes and function entries, not elapsed time. The exhaustive checks include empty inputs, duplicates and missing targets. The recurrence is a mathematical model; the lab does not actually recurse factorial to depth 1,024, which could exceed Python's recursion limit.

from functools import lru_cache
from itertools import product


def two_sum(a, target):
    seen = {}
    for i, x in enumerate(a):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i
    return None


def binary_probes(n, target):
    lo, hi, count = 0, n - 1, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        count += 1
        if mid == target:
            return count
        if mid < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return count


def fib_run(n, memo):
    calls = 0
    cache = {}
    def fib(k):
        nonlocal calls
        calls += 1  # includes calls that return a cached result
        if memo and k in cache:
            return cache[k]
        value = k if k < 2 else fib(k - 1) + fib(k - 2)
        if memo:
            cache[k] = value
        return value
    return fib(n), calls


def merge_cost(n):
    if n == 1:
        return 1
    return 2 * merge_cost(n // 2) + n


def shifts(n, k, insert):
    a = list(range(n))
    moves = 0
    if insert:
        a.append(None)  # spare slot; capacity growth not counted
        for j in range(n, k, -1):
            a[j] = a[j - 1]
            moves += 1
        a[k] = 'x'
    else:
        for j in range(k, n - 1):
            a[j] = a[j + 1]
            moves += 1
        a.pop()
    return moves


for n in (10, 100, 1000):
    linear = sum(1 for _ in range(n))
    square = sum(1 for _ in range(n) for _ in range(n))
    triangle = sum(1 for i in range(n) for _ in range(i))
    worst = max(binary_probes(n, x) for x in range(-1, n + 1))
    assert (linear, square, triangle, worst) == (
        n, n * n, n * (n - 1) // 2, n.bit_length())
    print('n, linear, square, triangle, binary:',
          n, linear, square, triangle, worst)

address_checks = 0
for rows in range(1, 9):
    for cols in range(1, 9):
        row = [(i, j) for i in range(rows) for j in range(cols)]
        col = [(i, j) for j in range(cols) for i in range(rows)]
        for i in range(rows):
            for j in range(cols):
                assert row.index((i, j)) == i * cols + j
                assert col.index((i, j)) == j * rows + i
                address_checks += 2
print('2D offset checks:', address_checks)
print('addresses:', 1000 + 99 * 4, 2000 + (2 * 4 + 1) * 2,
      2000 + (1 * 3 + 2) * 2, 500 + 7 * 8,
      100 + (3 * 6 + 2) * 4, 100 + (2 * 5 + 3) * 4)
print('n=10 shifts (start, middle, end):',
      [shifts(10, k, True) for k in (0, 5, 10)],
      [shifts(10, k, False) for k in (0, 5, 9)])
shift_checks = 0
for n in range(21):
    for k in range(n + 1):
        assert shifts(n, k, True) == n - k
        shift_checks += 1
    for k in range(n):
        assert shifts(n, k, False) == n - 1 - k
        shift_checks += 1
print('shift checks:', shift_checks)

pair_checks = 0
for n in range(7):
    for a in product((-1, 0, 1), repeat=n):
        for target in range(-3, 4):
            result = two_sum(a, target)
            exists = any(a[i] + a[j] == target
                         for i in range(n) for j in range(i + 1, n))
            assert (result is not None) == exists
            if result is not None:
                i, j = result
                assert 0 <= i < j < n and a[i] + a[j] == target
            pair_checks += 1
print('Two Sum checks:', pair_checks)
print('duplicates / no pair:', two_sum([3, 3], 6), two_sum([3], 6))
print('fib(10), naive / memo calls:', fib_run(10, False), fib_run(10, True))
assert fib_run(10, False) == (55, 177)
assert fib_run(10, True) == (55, 19)
for k in range(11):
    n = 2 ** k
    assert merge_cost(n) == n * (k + 1)
print('merge recurrence T(8), T(1024):', merge_cost(8), merge_cost(1024))
print('linear search successful average n=10:', sum(range(1, 11)) / 10)
print('3n^2+5n+2 over n^2 at n=1000:', (3*1000**2+5*1000+2)/1000**2)
print('ALL CHECKS PASSED')

Executed output

n, linear, square, triangle, binary: 10 10 100 45 4
n, linear, square, triangle, binary: 100 100 10000 4950 7
n, linear, square, triangle, binary: 1000 1000 1000000 499500 10
2D offset checks: 2592
addresses: 1396 2018 2010 556 180 152
n=10 shifts (start, middle, end): [10, 5, 0] [9, 4, 0]
shift checks: 441
Two Sum checks: 7651
duplicates / no pair: (0, 1) None
fib(10), naive / memo calls: (55, 177) (55, 19)
merge recurrence T(8), T(1024): 32 11264
linear search successful average n=10: 5.5
3n^2+5n+2 over n^2 at n=1000: 3.005002
ALL CHECKS PASSED

12. Questions this topic can ask, with answers

• Define an algorithm. A finite, clear sequence of steps that solves a problem.
• Difference between time and space complexity. Time counts steps; total space counts memory including input. Auxiliary space counts extra storage.
• Difference between O, Omega and Theta. O is an upper bound, Omega a lower bound, Theta both together (tight).
• Why is array access O(1)? The address formula needs one multiplication and one addition.
• Why is inserting in an array O(n)? Items after the position must shift.
• Numerical: find the address of a[i][j]. Use the two formulas in section 10.
• Short note on recursion. Base case, recursive case, call stack, example factorial, cost O(n) time and O(n) stack.
• Application: Two Sum with a dictionary in expected O(n) time and O(n) auxiliary space.

13. Practice with solutions

Q1. Simplify 4n² + 10n log n + 50.

O(n²). n² grows faster than n log n, and constants are dropped.

Q2. An array has base address 500 and 8-byte items. Find the address of a[7].

500 + 7 x 8 = 556.

Q3. A 5 x 6 array, base 100, size 4. Find a[3][2] in row-major and column-major.

Row-major: 100 + (3 x 6 + 2) x 4 = 180. Column-major: 100 + (2 x 5 + 3) x 4 = 152.

Q4. How many items move if you insert at index 3 in an array that holds 12 items?

12 - 3 = 9 items move.

Q5. Solve T(n) = 2T(n/2) + n, T(1) = 1, for n = 8 by counting.

T(8) = 32. By the formula n log2 n + n = 8 x 3 + 8 = 32, so O(n log n).

Q6. What is the time complexity of: for i in range(n): for j in range(i): ...

The inner loop runs 0 + 1 + ... + (n-1) = n(n-1)/2 times, so O(n²). For n = 100 that is 4,950.

Boundary answers

Question	Answer
Does O(n) mean exactly n operations?	No. It is an asymptotic upper bound, with constants and a large-input threshold.
Can Omega describe worst case?	Yes. Worst-case linear search has both O(n) and Omega(n), hence Theta(n).
Two Sum [3] with target 6?	None. The same element cannot be used twice.
Binary-search checks for n=0?	Zero. For n > 0, maximum probes are floor(log2 n)+1.
Why not fib for huge n with this code?	Naive branching repeats work; memoization still uses stack depth and large integers.
Can every recurrence use Master?	No. Check the divide-by-b shape and the nonrecursive term first.

14. Eight rules to remember

1. Complexity is growth, not seconds.
2. Drop constants and smaller terms.
3. Sequential steps add, nested steps multiply.
4. Exams mean worst case unless stated.
5. a[i] address = base + i x size.
6. Insert or delete in an array moves the items after it.
7. Recursion needs a base case and uses stack space.
8. T(n) = 2T(n/2) + n gives O(n log n).

Series: DSA in 30 Days index | Previous: none (this is Episode 1) | Next: Episode 2, searching and basic sorts

Related: Binary Search explained (the searching lesson), more time complexity problems and the Exam Numericals Hub.