0.1.2 Math toolkit: logarithms, floors and ceilings, sums (arithmetic, geometric, harmonic)

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

How many times does for (i = 1; i <= n; i += 2) run its body? from Lesson 0.1.1
What does "correct" mean for an algorithm? from Lesson 0.1.1
What is T(n)? from Lesson 0.1.1

1 · The Hook

🎣

Almost every running time in GATE is built from three things: logarithms (halving and doubling), floors and ceilings (whole steps), and sums (loops inside loops). With five formulas you can turn any loop into an exact count.

2 · Predict First

🤔

Start with n = 1,000 and keep halving (dropping fractions) until you reach 0. How many halvings? And how many bits does 1,000 have in binary?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1 → 0: 10 halvings. 1,000 needs 10 bits (2⁹ = 512 ≤ 1000 < 1024 = 2¹⁰). Both are ⌊log₂ 1000⌋ + 1.

Logarithms

log_b x = y means bʸ = x. In these notes log means log₂.

log(xy) = log x + log y; log(x/y) = log x − log y; log(xᵏ) = k log x.
Change of base: log_b x = log x / log b. So all log bases differ only by a constant factor.
Swap rule: a^(log_b n) = n^(log_b a). Example: 2^(log n) = n; 4^(log n) = n².
log 1 = 0; log 2 = 1; log 1024 = 10.

Halving and doubling

Halving n (dropping fractions) until it reaches 1 takes ⌊log n⌋ steps; until it reaches 0 takes ⌊log n⌋ + 1.
Doubling 1 until it is at least n takes ⌈log n⌉ steps.
n has ⌊log n⌋ + 1 bits.

Floors and ceilings

⌊x⌋ = largest integer ≤ x; ⌈x⌉ = smallest integer ≥ x. ⌊n/2⌋ + ⌈n/2⌉ = n for every integer n.

Sums

Sum	Closed form	Growth
1 + 2 + … + n	n(n + 1)/2	n²
1² + 2² + … + n²	n(n + 1)(2n + 1)/6	n³
1 + r + r² + … + rᵏ (r ≠ 1)	(rᵏ⁺¹ − 1)/(r − 1)	dominated by the largest term
1 + 2 + 4 + … + 2ᵏ	2ᵏ⁺¹ − 1	2 × the last term
1 + 1/2 + 1/3 + … + 1/n (harmonic Hₙ)	≈ ln n	log n
log 1 + log 2 + … + log n = log(n!)	≈ n log n	n log n

A geometric sum with r < 1 (like 1 + 1/2 + 1/4 + …) is less than 1/(1 − r): a constant (2 for r = 1/2).

4 · Visual

Halving 1000:   1000  500  250  125  62  31  15  7  3  1     <- 9 steps to reach 1 = floor(log2 1000)
Doubling to 1000:  1  2  4  8 ... 512  1024                  <- 10 steps = ceil(log2 1000)

Geometric:  1 + 2 + 4 + 8 + 16 = 31 = 2^5 - 1     (the total is about twice the last term)

n	8	16	1000	1024	10⁶
⌊log n⌋	3	4	9	10	19
⌈log n⌉	3	4	10	10	20

5 · Worked Examples

Example 1 Easy

Compute 1 + 2 + … + 100.

Solution

100 × 101 / 2 = 5,050.

Example 2 Medium

Simplify 8^(log n).

Solution

8^(log n) = n^(log 8) = n³.

Example 3 GATE

How many times does the body run?

for (i = n; i > 0; i = i / 2)
    count++;

for n = 100?

Solution

i = 100, 50, 25, 12, 6, 3, 1: 7 = ⌊log 100⌋ + 1.

6 · GATE Traps

⚠️

log means log₂ here; other bases differ only by a constant factor.
Halving to 1 takes ⌊log n⌋ steps; counting the start value too gives ⌊log n⌋ + 1 iterations.
1 + 2 + … + n is about n²/2, not n².
A decreasing geometric series sums to a constant.

7 · Memory Hook

🧠

"Halve = log, add-up-to-n = n²/2, doubling sum = twice the last."

8 · Connect the Dots

Chapter 0.1 is complete: steps and the math to count them. Chapter 0.2 recaps the data structures that algorithms run on, with the cost of each operation.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markArithmetic sum

1 + 2 + … + 50 = ?

Numerical answer: ________

Q2NAT1 markHalving loop

How many times does for (i = 1; i <= 64; i = i * 2) run its body?

Numerical answer: ________

Q3MCQ1 markSwap rule

n^(log 3) equals:

(A) n³
(B) 3^(log n)
(C) 3n
(D) log(3n)

Q4NAT2 marksGeometric sum

1 + 3 + 9 + 27 + 81 + 243 = ?

Numerical answer: ________

Q5NAT1 markBits

How many bits does the number 5,000 have in binary?

Numerical answer: ________

10 · Rule Card

log = log₂; bases differ by constants; a^(log_b n) = n^(log_b a).
Halving to 1: ⌊log n⌋ steps; n has ⌊log n⌋ + 1 bits; doubling to ≥ n: ⌈log n⌉.
Σi = n(n+1)/2; Σi² = n(n+1)(2n+1)/6; Σ2ⁱ (0..k) = 2ᵏ⁺¹ − 1; Hₙ ≈ ln n; log n! ≈ n log n.
Decreasing geometric series: constant.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

logarithm ruleschange of baseswap rule a^(log n)halving count ⌊log n⌋floor and ceilingarithmetic seriessum of squaresgeometric seriesharmonic number Hₙlog n!

12 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Recall Warm-up

⌈n/2⌉.
It halts with the right output on every instance.
The number of basic steps on an input of size n.