Algorithm Complexity Analysis from Code

Reading a loop and instantly knowing its time complexity is a GATE-CS reflex worth thousands of marks across mocks. Most students freeze on nested loops — but every loop pattern reduces to one of four templates, and once you recognise them you can write down Θ-notation almost without thinking.

Definition: The time complexity of a loop is the number of iterations of its body, expressed asymptotically (Big-O, Θ, Ω) in terms of the input size n.

Definition: Loops are classified as independent (inner loop bounds do not depend on outer indices) or dependent (inner bounds depend on outer indices).

The four loop templates — your entire toolkit

Almost every loop you see in a GATE question fits one of these four patterns. Master each one separately and the combinations become trivial.

1. Independent nested loops — multiply.

for (i = 1; i <= n; i++)
   for (j = 1; j <= n; j++)
      // O(1) work

The inner loop runs n times for each outer iteration. Total iterations = n × n = n². So this is Θ(n²). When the two bounds are independent of each other, you just multiply.

2. Dependent loops (j depends on i) — sum.

for (i = 1; i <= n; i++)
   for (j = 1; j <= i; j++)
      // O(1) work

Here the inner loop runs i times when the outer index is i. Total iterations = 1 + 2 + 3 + … + n = n(n+1)/2. Asymptotically this is still Θ(n²) — the constant ½ disappears in Big-Θ. The trick is recognising that the inner work changes from one outer pass to the next.

3. Geometric / halving loops — logarithm.

i = 1;
while (i < n) i = i * 2;

i takes values 1, 2, 4, 8, …, up to n. After k iterations, i = 2ᵏ. The loop stops when 2ᵏ ≥ n, i.e. k ≥ log₂ n. Total iterations ≈ log₂ n, complexity Θ(log n).

General rule: if j = j * k (multiplicative step) and j goes from 1 to limit, the iteration count is log_k(limit). The base of the logarithm is the multiplier. Asymptotically, all log bases collapse into Θ(log n).

The same pattern works for division: while (i > 1) i = i / 2; — that is also Θ(log n).

4. Outer linear, inner geometric — n log n.

for (i = 1; i <= n; i++) {
   j = 1;
   while (j < n) j = j * 2;
}

Outer runs n times; inner runs log n times each time. Total = n × log n = Θ(n log n) — the same complexity as merge sort and heap sort.

Worked example — the most common GATE trap

Question: Analyse the time complexity of

for (i = 1; i <= n; i = i * 2)
   for (j = 1; j <= i; j++)
      // O(1) work

Solution:

Step 1: Identify the outer-loop pattern. i takes the values 1, 2, 4, 8, …, up to n — a geometric loop with log₂ n iterations.

Step 2: Identify the inner-loop pattern. The inner loop runs i times when the outer index is i. So it is a dependent loop.

Step 3: Sum the inner counts across outer iterations:
1 + 2 + 4 + 8 + … + n/2 + n
= 2n − 1 (geometric series sum)
= Θ(n)

Step 4: There is no extra factor of log n. The total work is just Θ(n), even though the outer loop has log n iterations — because the inner iterations grow with i and the sum is dominated by the last term.

Conclusion: This nested loop is Θ(n), not Θ(n log n). A frequent exam trap — multiplying the bounds (log n × n) gives the wrong answer.

Shortcuts that save minutes in the exam

• For for (j = 1; j <= n; j = j * k) the iteration count is log_k n.
• For for (j = n; j >= 1; j = j / k) the iteration count is also log_k n.
• For two completely independent nested loops with bounds n and m, total = n × m.
• For dependent loops, write the summation: ∑_{i=1}^{n} (work of inner with bound depending on i), then evaluate.
• For a break or return inside the loop, distinguish best case from worst case — the worst case usually still iterates to the bound, but the best case might exit immediately.

Why it matters: GATE CS has 1–3 direct complexity-from-code MCQs every year; an additional 2–4 questions on algorithms (sorting, searching, DP) demand the same skill implicitly. Strong loop intuition shaves real seconds off every other algorithm question too.

Real-world example: Binary search halves the search space each iteration — exactly the i = i / 2 pattern — giving Θ(log n). Merge sort does Θ(log n) levels of recursion, with Θ(n) merging work per level — exactly the outer-linear × inner-log shape, giving Θ(n log n). Selection sort is the dependent nested-loop case (i + (i−1) + … + 1) — Θ(n²). The same four templates underlie every classical algorithm.

Common misconception: Students assume "outer loop runs A times, inner runs B times, so total is A × B." This is only true when the bounds are independent. For dependent loops, you must sum the inner counts. The sum 1 + 2 + … + n = n(n+1)/2 = Θ(n²) is the same as n × n asymptotically, but the dependent loop for j=1..i runs half as many iterations as the independent for j=1..n — and that constant matters in multi-step analyses.

Another trap: forgetting to specify which case. "Linear search" is Θ(1) best case (target at first position), Θ(n) average, Θ(n) worst case (target absent). State the case explicitly when you write the answer.

Memorize these closed forms used in loop analysis:

• 1 + 2 + ... + n = n(n+1)/2 = Theta(n^2)
• 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6 = Theta(n^3)
• 1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1 = Theta(2^k)
• Harmonic: 1 + 1/2 + 1/3 + ... + 1/n = Theta(log n) (H_n ~ ln n + 0.577)
• sum_{i=1}^{n} n/i = n.H_n = Theta(n log n)
• Geometric sum with ratio r>1: dominated by last term Theta(r^n).
  The harmonic sum is a frequent trap: a loop doing n/i work per outer iteration totals Theta(n log n), not Theta(n^2).

The Computer Aptitude section of the RPF Sub-Inspector exam routinely tests the everyday vocabulary of the World Wide Web — URL, HTTP, HTTPS, cookies, browsers, search engines. These look easy but are designed to catch candidates who confuse two similar-sounding terms. Get the definitions crisp and you guarantee 2–3 free marks.

Definition: A URL (Uniform Resource Locator) is the full web address of any resource on the internet. Its structure is protocol://host/path — for example https://www.indianrailways.gov.in/news/latest.

Definition: HTTP (HyperText Transfer Protocol) is the set of rules computers use to request and deliver web pages. It is stateless, meaning the server does not remember anything about you between two requests on its own.

Definition: HTTPS (HyperText Transfer Protocol Secure) is HTTP wrapped in an SSL/TLS encryption layer. The letter "s" literally stands for secure.

Definition: A cookie is a tiny text file a website asks your browser to store, so the site can remember your login, preferences, or shopping cart on later visits.

Definition: A web browser (Chrome, Firefox, Edge, Safari) is the client software that renders HTML into the visual page you see.

Definition: A search engine (Google, Bing, DuckDuckGo) is a service that indexes and finds content on the web — it does not display the page itself.

How a URL Is Built

Take https://www.irctc.co.in/nget/train-search. The first part — https — is the protocol, telling your browser which language to speak with the server. The :// is a separator. www.irctc.co.in is the host, the human-readable address of the server. /nget/train-search is the path, pointing to the specific page on that server. Some URLs also carry a port number after the host (:443 for HTTPS by default), query parameters after a ?, and a fragment after a #. In the RPF SI exam, recognising the protocol and host in a URL is the most common question shape.

HTTP vs HTTPS — Why the Padlock Matters

When you load a normal HTTP page, every byte travels in plain text. Anyone on the same Wi-Fi network — say, a free railway-station hotspot — could read your password or OTP. HTTPS solves this by wrapping the data inside SSL/TLS encryption. Modern browsers show a padlock icon beside the URL, and the address starts with https://. If a banking or government site shows http:// without the s, treat it as suspicious. HTTPS does not just protect privacy; it also confirms (via the site's certificate) that you actually reached the real server and not an attacker's lookalike.

Why it matters: As a Sub-Inspector posted at a major railway station, you may have to advise commuters who fall victim to phishing — a fake irctc-refund.in page over plain HTTP designed to steal card details. Knowing the difference between HTTP and HTTPS is part of basic cyber awareness training in the Railway Protection Force.

What Cookies Actually Do

A cookie is just a name = value text record like sessionid = a83fk2…. The server hands it to your browser the first time you log in; the browser sends it back with every subsequent request, and the server uses it as a wristband — "ah, this is the same user". That is how Flipkart keeps your cart full after you close the tab, how Gmail keeps you logged in for weeks, and how a news site remembers your dark-mode choice.

Cookies come in flavours: session cookies disappear when you close the browser; persistent cookies live until an expiry date; third-party cookies are placed by domains other than the one you visited (these are used for ad tracking and are increasingly blocked).

Common misconception: Many learners think cookies are spyware or viruses. They are not — a cookie is a passive text file that cannot execute code. The privacy concern is about what data the site chooses to put inside it (tracking IDs, behaviour logs), not the cookie mechanism itself.

Browser vs Search Engine — The Most Tested Confusion

Examiners regularly pose: "Which of the following is a search engine? (A) Chrome (B) Safari (C) Google (D) Edge". The correct answer is Google. Chrome, Safari, and Edge are all browsers — programs you install. Google is a search engine — a website you visit through a browser to find other pages. You can use Bing inside Chrome, or Google inside Edge, because the two are independent layers.

HTML and Hyperlinks

Definition: HTML (HyperText Markup Language) is the language used to describe a web page's structure — headings, paragraphs, images, links — using tags like <h1> and <p>. The browser reads the HTML and draws it.

Definition: A hyperlink is the clickable cross-reference between two web pages, written in HTML using the <a href="..."> tag. The web is called a "web" precisely because hyperlinks form a network connecting documents across servers.

Real-world example: When you click "Check PNR Status" on the IRCTC home page, your browser sends an HTTPS request to www.irctc.co.in, which checks your session cookie, fetches your booking from a railway database, builds an HTML response, and the browser renders it as a neat status table. URL, HTTPS, cookie, browser, and HTML — five concepts in one click.

A Quick Worked Example

Question: In the URL https://services.india.gov.in/forms/aadhaar?lang=hi, identify (a) the protocol, (b) the host, and (c) state whether the connection is encrypted.

Solution:

Step 1: Read up to ://. The protocol is https.

Step 2: Read from after :// up to the next /. The host is services.india.gov.in.

Step 3: Since the protocol is HTTPS, the connection is encrypted by SSL/TLS.

Conclusion: Protocol = HTTPS, Host = services.india.gov.in, Connection is encrypted.

Cover the answer, recall, then check. 12 GATE cards on deriving complexity from loops.

Q1. for i=1..n: for j=1..n: O(1) — complexity?
A1. Θ(n²) — two independent linear loops multiply.

Q2. for i=1..n: for j=1..i: O(1) (triangular) — complexity?
A2. Θ(n²) — Σi = n(n+1)/2.

Q3. for(i=1; i<=n; i*=2) — complexity?
A3. Θ(log n) — i doubles, so ~log₂n iterations.

Q4. for(i=2; i<=n; i=i*i) — complexity?
A4. Θ(log log n) — the exponent doubles each step (i = 2^(2^k)).

Q5. Two separate sequential loops, each O(n) — total?
A5. Θ(n) — O(n) + O(n) = O(n); sequential blocks add, dominated by the max.

Q6. while(n>0) n = n/2 — complexity?
A6. Θ(log n).

Q7. for i=1..n: for(j=1; j<=n; j*=2) — complexity?
A7. Θ(n log n) — outer n times inner log n.

Q8. The classic harmonic double loop: for i=1..n: for(j=1; j<=n; j+=i) — complexity?
A8. Θ(n log n) — inner runs n/i times; Σ(n/i) = n·Hₙ = Θ(n log n).

Q9. Recursive f(n) that calls f(n−1) twice with O(1) work — complexity?
A9. Θ(2ⁿ) — recurrence T(n) = 2T(n−1) + O(1).

Q10. Work n + n/2 + n/4 + … + 1 across recursion levels — total?
A10. Θ(n) — geometric series sums to 2n − 1.

Q11. for(i=1; i<=n; i++) for(j=i; j<=n; j*=2) — complexity?
A11. Θ(n log n) — inner is Θ(log(n/i)); Σ log(n/i) = log(nⁿ/n!) = Θ(n) via Stirling… actually Σ_{i=1}^n log(n/i) = n log n − log n! = Θ(n). So total is Θ(n). (Trap: it is Θ(n), not Θ(n log n).)

Q12. Why can a loop's bound differ from its exact iteration count?
A12. Because asymptotics count growth: for(i=n; i>1; i/=2) runs ⌊log₂n⌋ times = Θ(log n) regardless of the exact floor.

Reading a code fragment and reporting its time complexity is one of the most frequently tested GATE skills — nearly every year a snippet of nested loops or a recursive function appears. The marks are easy if you know the standard loop patterns and the two summations (arithmetic and harmonic) that keep recurring; they are lost by rushing an off-by-a-log answer.

Core rules

• Independent nested loops multiply; sequential blocks add (dominated by the max).
• Additive step (i += c or i++) ⇒ linear number of iterations.
• *Multiplicative step (i = c) ⇒ logarithmic (Θ(log n)); i = i*i ⇒ Θ(log log n).
• Triangular loop (j to i) ⇒ Σi = Θ(n²).
• Harmonic loop (step += i) ⇒ Σ(n/i) = n·Hₙ = Θ(n log n).

Pattern cheat-sheet

Code pattern	Complexity
i++ , j++ (nested)	Θ(n²)
j from 1 to i	Θ(n²)
i *= 2	Θ(log n)
i = i*i	Θ(log log n)
outer n, inner ×2	Θ(n log n)
step j += i (harmonic)	Θ(n log n)
n/2 + n/4 + … (geometric)	Θ(n)
f(n−1) called twice	Θ(2ⁿ)

Exam Tricks & Tips

• 🎯 Count iterations, not statements — the loop variable's update rule decides log vs linear.
• 🎯 Multiplicative update ⇒ log: i *= k runs log_k n times; nested inside i++ gives Θ(n log n).
• 🎯 Spot the harmonic sum: whenever the inner count is n/i summed over i, it is Θ(n log n), a favourite trap disguised as Θ(n²) or Θ(n).
• 🎯 i = i*i is Θ(log log n) — the exponent itself doubles; do not misread it as Θ(log n).
• 🎯 Geometric work across recursion levels collapses to Θ(top level) — n + n/2 + … = Θ(n), not Θ(n log n).
• ❌ Common mistake: multiplying loop bounds blindly. for i=1..n: for(j=i; j<=n; j*=2) looks like n log n but sums to Θ(n) — always evaluate the actual summation.

Expected exam pattern

A 2-mark snippet: nested loops with mixed additive/multiplicative updates, or a short recursive function. You must derive the recurrence/summation and pick the tight Θ. Traps: harmonic sums, i*i, and geometric collapses.

Quick recap

Multiply independent nested loops, add sequential ones. Additive update → linear, multiplicative → log, square → log log. Learn Σi = Θ(n²) and Σ(n/i) = Θ(n log n) cold, and always compute the real summation before answering.