Tag complexity questions

Practice Questions on Time Complexity Analysis: A Comprehensive Tutorial

Time complexity analysis is a fundamental skill for algorithm design and optimization. Practice questions help develop the ability to analyze code and determine its efficiency. This tutorial provides an in-depth collection of time complexity practice questions with detailed explanations and C implementations.

This tutorial covers common time complexity patterns, loop analysis, nested loops, logarithmic loops, and practical examples to master complexity analysis.

---

Conceptual Introduction & Fundamentals

What is Time Complexity Analysis?

Time complexity analysis determines how an algorithm’s running time grows with input size. It counts the number of primitive operations performed as a function of input size, expressed using Big-O notation.

Why Practice Time Complexity Questions?

• Algorithm comparison: Choose efficient algorithms.
• Code optimization: Identify and fix performance bottlenecks.
• Interview preparation: Common interview topic.
• Problem-solving: Understand algorithm behavior.
• Theoretical understanding: Analyze growth rates.

Key Concepts

Concept	Description
Consecutive loops	Complexities add: O(n) + O(m) = O(n+m)
Nested loops	Complexities multiply: O(n) × O(m) = O(n×m)
Dividing loops	Loop variable divided by constant → O(log n)
Independent variables	Cannot combine n and m

Common Loop Patterns

Pattern	Complexity
for (i = 0; i < n; i++)	O(n)
for (i = 0; i < n; i *= 2)	O(log n)
for (i = 0; i < n; i++) for (j = 0; j < n; j++)	O(n²)
while (n > 0) n /= 2	O(log n)
for (i = 0; i < n; i++) for (j = i; j < n; j++)	O(n²/2) = O(n²)

---

Practice Questions with Solutions

Question 1: Consecutive Loops

c

#include <stdio.h> #include <stdlib.h> /* Time: O(N + M), Space: O(1) */ void consecutiveLoops(int N, int M) { int a = 0, b = 0; /* First loop: O(N) */ for (int i = 0; i < N; i++) { a = a + rand(); } /* Second loop: O(M) */ for (int j = 0; j < M; j++) { b = b + rand(); } } int main(void) { consecutiveLoops(100, 50); printf("Consecutive loops: O(N + M) time, O(1) space\n"); return 0; }

Answer: O(N + M) time, O(1) space

Explanation: First loop is O(N), second is O(M). Since N and M are independent, total is O(N+M). Variables are fixed size, so O(1) space.

Question 2: Nested Loop with Decreasing Inner Bound

c

#include <stdio.h> /* Time: O(N²) */ void nestedDecreasingLoop(int N) { int a = 0; for (int i = 0; i < N; i++) { for (int j = N; j > i; j--) { a = a + i + j; } } } int main(void) { nestedDecreasingLoop(10); printf("Nested decreasing loop: O(N²)\n"); printf("Total iterations: N + (N-1) + ... + 1 = N(N+1)/2\n"); return 0; }

Answer: O(N²)

Explanation: Total iterations = N + (N-1) + (N-2) + … + 1 + 0 = N(N+1)/2 = O(N²).

Question 3: Nested Loop with Doubling Inner

c

#include <stdio.h> /* Time: O(N log N) */ void nestedDoublingLoop(int n) { int k = 0; for (int i = n / 2; i <= n; i++) { // O(n/2) for (int j = 2; j <= n; j = j * 2) { // O(log n) k = k + n / 2; } } } int main(void) { nestedDoublingLoop(16); printf("Nested doubling loop: O(n log n)\n"); printf("Outer: n/2 iterations, Inner: log n iterations\n"); return 0; }

Answer: O(n log n)

Explanation: Outer loop runs n/2 times. Inner loop doubles j, so it runs log(n) times. Total = O(n/2 × log n) = O(n log n).

Question 4: Dividing Loop

c

#include <stdio.h> /* Time: O(log N) */ void dividingLoop(int N) { int a = 0, i = N; while (i > 0) { a += i; i /= 2; // Divides by 2 each iteration } } int main(void) { dividingLoop(16); printf("Dividing loop: O(log N)\n"); printf("Find smallest x such that N/2^x < 1, i.e., 2^x > N\n"); printf("x = log(N)\n"); return 0; }

Answer: O(log N)

Question 5: Loop with Multiplication

c

#include <stdio.h> /* Time: O(logₖ n) */ void multiplicationLoop(int n, int k) { for (int i = 1; i < n; i++) { i *= k; // Multiplies by k each iteration } } int main(void) { multiplicationLoop(100, 3); printf("Multiplication loop: O(log base k of n)\n"); printf("Loop runs k^c times where k^c = n, so c = logₖ(n)\n"); return 0; }

Answer: O(logₖ n)

Question 6: Nested Loop with Triangular Pattern

c

#include <stdio.h> /* Time: O(n²) */ void triangularLoop(int n) { int value = 0; for (int i = 0; i < n; i++) { // O(n) for (int j = 0; j < i; j++) { // O(i) value += 1; } } /* Total: 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 */ } int main(void) { triangularLoop(10); printf("Triangular loop: O(n(n-1)/2) = O(n²)\n"); return 0; }

Answer: O(n(n-1)/2) = O(n²)

---

Full Practical Code Example with Explanation

This program demonstrates all practice questions with measurable operation counts.

Program: Time Complexity Practice Analyzer

c

/** * time_complexity_practice.c * Demonstrates time complexity practice questions with solutions. * Includes operation counting for verification. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #include <errno.h> #include <math.h> #define MAX_LINE_LEN 100 /* Function prototypes */ void demonstrateConsecutiveLoops(int N, int M); void demonstrateNestedDecreasing(int N); void demonstrateNestedDoubling(int n); void demonstrateDividingLoop(int N); void demonstrateMultiplicationLoop(int n, int k); void demonstrateTriangularLoop(int n); void countOperations(void); void demonstrateAllQuestions(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Time Complexity Practice Questions ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Consecutive Loops O(N+M)\n"); printf("2. Nested Decreasing O(N²)\n"); printf("3. Nested Doubling O(N log N)\n"); printf("4. Dividing Loop O(log N)\n"); printf("5. Multiplication Loop O(logₖ N)\n"); printf("6. Triangular Loop O(N²)\n"); printf("7. Operation Counting\n"); printf("8. All Questions Demo\n"); printf("9. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demonstrateConsecutiveLoops(100, 50); break; case 2: demonstrateNestedDecreasing(10); break; case 3: demonstrateNestedDoubling(16); break; case 4: demonstrateDividingLoop(16); break; case 5: demonstrateMultiplicationLoop(100, 3); break; case 6: demonstrateTriangularLoop(10); break; case 7: countOperations(); break; case 8: demonstrateAllQuestions(); break; case 9: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Question 1: O(N+M) */ void demonstrateConsecutiveLoops(int N, int M) { printf("\n=== Consecutive Loops O(N+M) ===\n"); int operations = 0; int a = 0, b = 0; for (int i = 0; i < N; i++) { a = a + rand(); operations++; } for (int j = 0; j < M; j++) { b = b + rand(); operations++; } printf("N=%d, M=%d\n", N, M); printf("Total operations: %d (N+M=%d)\n", operations, N + M); printf("Time: O(N+M), Space: O(1)\n"); } /* Question 2: O(N²) */ void demonstrateNestedDecreasing(int N) { printf("\n=== Nested Decreasing O(N²) ===\n"); int operations = 0; int a = 0; for (int i = 0; i < N; i++) { for (int j = N; j > i; j--) { a = a + i + j; operations++; } } printf("N=%d\n", N); printf("Total operations: %d\n", operations); printf("Expected: N(N+1)/2 = %d\n", N * (N + 1) / 2); printf("Time: O(N²)\n"); } /* Question 3: O(N log N) */ void demonstrateNestedDoubling(int n) { printf("\n=== Nested Doubling O(N log N) ===\n"); int operations = 0; int k = 0; for (int i = n / 2; i <= n; i++) { for (int j = 2; j <= n; j = j * 2) { k = k + n / 2; operations++; } } printf("n=%d\n", n); printf("Total operations: %d\n", operations); printf("Expected: (n/2 + 1) × log2(n) ≈ %d\n", (n / 2 + 1) * (int)log2(n)); printf("Time: O(n log n)\n"); } /* Question 4: O(log N) */ void demonstrateDividingLoop(int N) { printf("\n=== Dividing Loop O(log N) ===\n"); int operations = 0; int a = 0; int i = N; while (i > 0) { a += i; i /= 2; operations++; } printf("N=%d\n", N); printf("Total operations: %d\n", operations); printf("Expected: log2(%d)+1 = %.0f\n", N, log2(N) + 1); printf("Time: O(log N)\n"); } /* Question 5: O(logₖ N) */ void demonstrateMultiplicationLoop(int n, int k) { printf("\n=== Multiplication Loop O(logₖ N) ===\n"); int operations = 0; int i = 1; while (i < n) { i *= k; operations++; } printf("n=%d, k=%d\n", n, k); printf("Total operations: %d\n", operations); printf("Expected: logₖ(n) = %.2f\n", log(n) / log(k)); printf("Time: O(logₖ n)\n"); } /* Question 6: O(n²) */ void demonstrateTriangularLoop(int n) { printf("\n=== Triangular Loop O(n²) ===\n"); int operations = 0; int value = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { value += 1; operations++; } } printf("n=%d\n", n); printf("Total operations: %d\n", operations); printf("Expected: n(n-1)/2 = %d\n", n * (n - 1) / 2); printf("Time: O(n²)\n"); } /* Counts operations for all patterns */ void countOperations(void) { printf("\n=== Operation Counting ===\n"); int n = 10; /* O(n) */ int linearOps = 0; for (int i = 0; i < n; i++) linearOps++; printf("O(n) for n=%d: %d operations\n", n, linearOps); /* O(log n) */ int logOps = 0; for (int i = 1; i <= n; i *= 2) logOps++; printf("O(log n) for n=%d: %d operations\n", n, logOps); /* O(n²) */ int quadraticOps = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) quadraticOps++; printf("O(n²) for n=%d: %d operations\n", n, quadraticOps); /* O(n log n) */ int linearithmicOps = 0; for (int i = 0; i < n; i++) for (int j = 1; j <= n; j *= 2) linearithmicOps++; printf("O(n log n) for n=%d: %d operations\n", n, linearithmicOps); } /* Demonstrates all questions briefly */ void demonstrateAllQuestions(void) { printf("\n=== All Questions Demo ===\n"); demonstrateConsecutiveLoops(5, 3); demonstrateNestedDecreasing(5); demonstrateNestedDoubling(8); demonstrateDividingLoop(8); demonstrateMultiplicationLoop(50, 2); demonstrateTriangularLoop(5); }

Expected Output (partial)

text

=== Time Complexity Practice Questions === --- Menu --- 1. Consecutive Loops O(N+M) 2. Nested Decreasing O(N²) 3. Nested Doubling O(N log N) 4. Dividing Loop O(log N) 5. Multiplication Loop O(logₖ N) 6. Triangular Loop O(N²) 7. Operation Counting 8. All Questions Demo 9. Exit Enter choice: 7 === Operation Counting === O(n) for n=10: 10 operations O(log n) for n=10: 4 operations O(n²) for n=10: 100 operations O(n log n) for n=10: 40 operations

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Confusing Consecutive vs Nested Loops

Consecutive loops add; nested loops multiply.

c

/* O(n + n) = O(n) */ for (int i = 0; i < n; i++) { ... } for (int j = 0; j < n; j++) { ... } /* O(n × n) = O(n²) */ for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { ... }

Solution: Count total operations carefully.

2. Not Recognizing Logarithmic Loops

Multiplication/division by constant indicates O(log n).

c

for (int i = 1; i <= n; i *= 2) // O(log n) for (int i = n; i > 0; i /= 2) // O(log n)

3. Overlooking Inner Loop Dependency

Inner loop bounds may depend on outer variable.

c

/* O(n²/2) = O(n²), not O(n²) */ for (int i = 0; i < n; i++) for (int j = i; j < n; j++) { ... }

Solution: Sum inner loop iterations.

4. Ignoring Independent Variables

N and M are independent; cannot combine.

c

/* O(N + M), not O(N²) */ for (int i = 0; i < N; i++) { ... } for (int j = 0; j < M; j++) { ... }

5. Not Validating with Actual Counting

Theoretical analysis may have errors.

Solution: Count operations to verify.

6. Integer Overflow in Operation Counts

Large counts overflow int.

Solution: Use long long or size_t.

7. Memory Leaks

Forgetting to free dynamically allocated memory.

Solution: Always free allocated memory.

8. Stack Overflow with Recursion

Deep recursion exhausts stack.

Solution: Use iterative approaches.

9. Not Handling Edge Cases

n=0 or n=1 need special handling.

Solution: Test with boundary values.

10. Memory Considerations

• Time complexity analysis focuses on operations, not memory.
• Space complexity must be analyzed separately.
• Algorithms may trade time for space or vice versa.

---

Summary & Best Practices

Practice questions on time complexity help develop the skill of analyzing algorithm efficiency. Regular practice with varied patterns is essential for mastery.

Key Takeaways

• Consecutive loops: O(n+m).
• Nested loops: O(n×m).
• Dividing/multiplying loops: O(log n).
• Triangular loops: O(n²/2) = O(n²).
• Independent variables cannot be combined.
• Count operations for verification.

Best Practices

1. Practice analyzing diverse loop patterns.
2. Count operations to verify analysis.
3. Recognize logarithmic patterns.
4. Distinguish nested from consecutive loops.
5. Consider inner loop dependencies.
6. Handle independent variables correctly.
7. Document complexity in comments.
8. Test with different input sizes.
9. Use appropriate data types.
10. Analyze both time and space.

By mastering time complexity analysis, you’ll make informed decisions about algorithm selection and write efficient code.