Introduction to Programming in C

📘 Time and Space Complexity (Analysis for C Programs)

Time and Space Complexity help us measure the efficiency of algorithms. Understanding them enables you to choose better logic, write optimized code, and crack technical interviews confidently.

⏱ What is Time Complexity?

Time Complexity is the amount of time taken by an algorithm to run as a function of input size n. It describes how performance scales with data growth.

Common Time Complexities:

• O(1) – Constant Time (e.g., array access)
• O(log n) – Logarithmic Time (e.g., Binary Search)
• O(n) – Linear Time (e.g., Linear Search)
• O(n log n) – Linearithmic Time (e.g., Merge Sort)
• O(n²) – Quadratic Time (e.g., Nested loops)
• O(2ⁿ), O(n!) – Exponential and Factorial (e.g., Recursion-heavy problems)

🔢 What is Space Complexity?

Space Complexity is the amount of memory used by an algorithm as a function of input size n, including variables, data structures, function calls, and more.

Examples:

• O(1) – Constant Space (using a few variables)
• O(n) – Storing an array of n elements
• O(n²) – Using a 2D array (like matrices)

🧠 Why It Matters?

• Helps identify slow or inefficient programs
• Crucial for competitive programming & technical interviews
• Important when working with large data sets or limited memory

📚 UdaanPath Example

Suppose UdaanPath is storing and sorting student scores. Choosing Merge Sort (O(n log n)) instead of Bubble Sort (O(n²)) makes it faster for thousands of entries.

🧮 Complexity Analysis Tips

• Analyze for loops: Each loop adds a factor of n
• Nested loops: O(n²) or more
• Recursive calls: Solve using recurrence relations or recursion trees
• Space usage: Count extra variables, arrays, and recursion stack

📊 Time vs Space Trade-Off

Sometimes, you can reduce time at the cost of space (e.g., storing computed results in DP arrays). Know your use case!

📝 Practice Tasks

1. Find time and space complexity of Linear Search
2. Analyze recursive factorial function
3. Compare Merge Sort vs Bubble Sort for time complexity
4. Write a loop that prints pairs and determine its complexity

✅ Summary

• Time complexity tells how fast your code runs
• Space complexity tells how much memory it consumes
• O(1), O(n), O(n log n), etc., help evaluate performance
• Essential for writing optimized, scalable C programs

🚀 Coming Next

It’s project time! Next, you’ll build a Student Record System in C — a great way to apply all the concepts you’ve learned so far.