Understanding Time and Space Complexity in DSA (Beginner-Friendly)

🧠 Introduction

If you're starting your DSA (Data Structures and Algorithms) journey, you've probably heard how important Time and Space Complexity are. But what exactly do they mean, and why should you care?

In this blog, we’ll break down these fundamental concepts in a simple and beginner-friendly way. Whether you’re solving coding problems, preparing for interviews, or just curious to know how efficient your code is—understanding complexity is key.

When we write code, it's not just about getting the correct output. It's also about how fast our code runs (⏱ Time Complexity) and how much memory it uses (💾 Space Complexity). These two factors help us measure the performance of any algorithm.

As someone who is learning DSA from scratch, I’m documenting my learnings here to help other learners like me. I’ve also included visual aids, relatable examples, and some notes from my college YouTube channel and trusted websites—so you’ll get a well-rounded understanding in one place.

Let’s dive into the world of analyzing code smartly! ✨

📚 Table of Contents

1. What is Time Complexity?

2. Why Time Complexity Matters

3. Big O Notation with example

4. Graph of  Time Complexity 

5. Different Types of Time Complexities

6. What is Space Complexity?

7. Question to solve

8. practical usage

9. Conclusion

---

⏱️ What is Time Complexity? (My Understanding)

Time complexity doesn't refer to the actual time taken by the machine. Instead, it refers to the amount of time an algorithm takes as a function of the input size (n).

In time complexity, there are two main things:

1. Input size (e.g., n = 10)

2. Operation behavior (e.g., int x = 10; is one operation)

In many cases, the number of operations depends directly on the input size.

---

📊 For example:

Input Size (n)	Operation Behavior f(n)
n = 1	1 operation
n = 20	20 operations
n = 300	300 operations

💻 Let’s relax and understand it with a coding example of Linear Search:

for (int i = 0; i < n; i++) {
    if (arr[i] == tar) {
        return i;
    }
}
return -1; // if not found

 

📊 Graphical Representation of Time Complexity in Linear Search

Explanation: The time complexity is O(n), also known as Big O of n. It represents a linear relationship between input size and operations, which appears as a straight line on the graph.

🚀 Why Time Complexity Matters

At first, Time Complexity might seem like just a textbook term. But in reality, it’s the key to writing efficient and scalable code—and avoiding slow, laggy programs.

---

🔥 Real-World Relevance

Picture this:
Your app works great with 10 users. But suddenly, it’s handling 10,000+ users and everything slows to a crawl. That’s where Time Complexity steps in—it tells you how well your code will perform as input grows.

---

🧮 What It Tells Us

Time complexity helps us analyze how fast an algorithm runs as the input size increases. It’s like knowing whether your solution will sprint or stumble when the data scales up.

---

💡 Why It’s a Big Deal

• Helps choose better, faster algorithms

• Makes your code scalable and reliable

• Prepares you for coding interviews

• Avoids the “it works, but it’s too slow” problem

---

🎯 Final Word

You don’t need to memorize every complexity rule, but understanding why it matters helps you write code that’s not just correct—but smart and future-ready. 🚀

🧠 Understanding Big O Notation – The Performance Indicator

Big O Notation is a way to describe how the performance of an algorithm changes as the size of the input grows. It doesn’t measure actual time—it focuses on how fast the number of operations increases relative to input size (n).

Think of it as the “speed rating” of your algorithm as the input gets bigger.

---

🎯 Big O – Focus on the Worst Case

Big O typically represents the worst-case scenario—the maximum time or steps an algorithm will take. It is also known as Upper-Bound.

For example:

• Searching in an unsorted array: O(n) – You may have to check every element.

• Binary search in a sorted array: O(log n) – Each step cuts the search space in half.

---

📊 Best, Average, and Worst Case Explained

An algorithm’s time complexity can vary depending on the input. That’s why we also consider:

Case	Description	Notation
Best Case(Lower- bound)	The fastest scenario (everything goes right)	Ω (Omega)
Average Case(Theta)	The expected scenario over many runs	Θ (Theta)
Worst Case(Upper-Bound)	The slowest scenario (Big O focuses here)	O (Big O)

👇 Quick Example: Linear Search in an Array

Suppose you’re searching for a number in an array of size n:

• Best Case (Ω(1)): It’s the first element.

• Average Case (Θ(n/2)): It’s somewhere in the middle.

• Worst Case (O(n)): It’s the last element or not present at all.

📐 Some Mathematical Examples to Find Time Complexity

• To find time complexity, we follow two simple rules:

  1. Ignore constants like numbers (1, 2, 3, etc.).

  2. Always consider the largest term in the equation.
     For example: In (n² + n), the larger term is n².

  ---

🤔 Feeling confused? Let’s clear it up with a few examples:

🧮 Example 1:

• 4n² + 3n + 5
  → Ignore constants → n² + n + 1  (Rule 1)
  → Pick the largest term → n²   (Rule 2)

🧮 Example 2:

• 100 + 5n² + √n
  → Ignore constants → 1 + n² + √n
  → Pick the largest term → n²

  ✅ So, the time complexity of both equations is O(n²)

  ---

📝 In Short:

• • Simply ignore constant numbers like 4, 3, 5, 100, etc.

  • If an expression has no variable (like just 5 or 100), replace it with 1.

  • Then, choose the term with the highest growth rate, like n².

💪 Now Try Some Examples On Your Own for Practice! 👍😍

✅ Why Focus on the Worst Case?

In real-world scenarios and interviews, you plan for the worst—because that's when your code might be under the most pressure. Big O helps you guarantee performance even in the toughest situations.

📈 Graph of Time Complexity – Visualizing Growth

When learning time complexity, graphs make everything easier to understand. They help us visualize how different algorithms grow as input size increases.

---

🧠 Why Use a Graph?

Text tells us what an algorithm does.
But graphs show us how fast it grows — and how it performs compared to others.

🧮 Plotting Time Complexities

Let’s look at a graph comparing some common complexities:

• O(1) → Flat line. Constant, no matter the input.

• O(log n) → Slowly rising curve. Very efficient.

• O(n) → Straight line. Grows linearly.

• O(n log n) → Grows faster than linear but still manageable.

• O(n²) → Steep curve. Slows down quickly with large input.

• O(2ⁿ) → Skyrocket! Not practical for big inputs.

---

📊 Sample Graph Behavior

As n increases, efficient algorithms (like O(log n)) grow slowly,
while inefficient ones (like O(2ⁿ)) become unusable at large scale.

---

🎯 Conclusion

A time complexity graph is your cheat sheet for choosing smarter algorithms.
When in doubt, plot it out! 📊✨

⏰ Different Types of Time Complexity

When we analyze an algorithm, we often describe its efficiency using time complexity. It helps us understand how the algorithm's running time grows as the input size increases. Below are some commonly used time complexities, from the fastest to the slowest.

I’m sharing my understanding of different types of time complexity along with practical examples. So let’s crack the concept of time complexity together! 😍

---

🟢 O(1) – Constant Time

The execution time remains the same regardless of the input size.
It is the fastest and most efficient time complexity.

In this type, we always perform a constant operation, meaning the same task is done, no matter how big the input is.

🔧 Example:

the program is in c+ +:

int n;  
cin >> n;  
int ans = n * (n + 1) / 2;

All these operations are completed in a single step each, so the time complexity is O(1).

✅ Other Examples:

• Calculating the sum of numbers from 1 to n using a formula

• Accessing an element directly in an array (arr[i]).

🔹 O(log n) – Logarithmic Time

When an algorithm reduces the size of the input data in each step (typically by half), its time complexity is said to be logarithmic. That means instead of checking each item one by one, we eliminate a large portion of the data with each operation.

This is much faster than linear time, especially with large inputs!

✅ When do we get O(log n)?

• When we divide the problem into halves (or other fractions) at every step.

• Binary Search is the most classic and practical example.

---

🔧 Example – Binary Search

Suppose you have a sorted array of numbers, and you want to find a specific value.

Instead of checking each element one by one:

1. You check the middle element.

2. If it's not the answer, you cut the array in half and continue.

3. You keep dividing until the value is found or not found.

int binarySearch(int arr[], int n, int key) {
    int start = 0, end = n - 1;
    while (start <= end) {
        int mid = (start + end) / 2;
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] < key)
            start = mid + 1;
        else
            end = mid - 1;
    }
    return -1;
}

Each iteration reduces the problem size by half, so the time complexity is O(log n).

👉Binary Search Time Complexity Explained Visually

🕒 O(n) – Linear Time Complexity

When an algorithm’s running time grows directly in proportion to the size of the input, we say it has linear time complexity, denoted as O(n).

✅ Definition:
For each new element added to the input, the algorithm does one additional step. So if the input size is n, the algorithm runs n operations.

---

🔍 Real-Life Analogy:

Imagine searching for your name in a guest list with no order. You start from the top and check each name one by one — the more names in the list, the longer it takes.

---

🧠 Code Example (C++):

Example 1: Sum of n number

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += i;
}

Example 2: N factorial

       int fact =1;

       for(int i=1; i<=n; i++){

             fact*i;

          }

Example 3: Kadane Algorithm

           int currSum=0, ans=INT_MIN;

           for(int i =0; i<n; i++){

               currSum +=arr[i];

               ans = max(currSum,ans);

               currSum= currSum< 0 ? 0 : currSum;   //Using of ternary statement

In this loop:

• The code executes n times,

• So the time complexity is O(n).

---

💡 More Practical Examples:

• Finding the maximum element in an unsorted array.

• Printing all elements of a list or array.

• Linear search in an array (checking every item one by one).

---

🔁 Why It Matters:

Linear time is still efficient for small and moderate-sized inputs, but can become slower as input grows.
Compared to constant time O(1), this is slower, but still manageable and widely used.

🔹  O(n log n) 

• "n" is the number of elements in the input.

• "log n" typically refers to logarithm base 2 (log₂n).

• So, the algorithm does slightly more work than linear (O(n)) but less than quadratic (O(n²)).

🔹 Where does it appear?

This time complexity is common in:

• Efficient sorting algorithms:

  • Merge Sort

  • Heap Sort

  • Quick Sort (average case)

• Divide and conquer algorithms

  • Like when a problem is divided in half each time and each half takes O(n) time to process.

🔹 Intuitive example:

Imagine splitting an array into halves until each element stands alone (like Merge Sort). That’s the log n part. Then merging them back together takes n time. So total = n * log n.

🔹 O(n²) — Quadratic Time Complexity

This means that as the input size grows, the time taken grows proportional to the square of the input size.

🔸 Example:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // constant-time operation
    }
}

✅ Here, the inner loop runs n times for every n iterations of the outer loop ⇒ n * n = n²

🔸 Where you see it:

• Bubble Sort

• Selection Sort

• Insertion Sort (worst case)

• Brute-force algorithms (like checking all pairs of items)

---

🔹 O(n³) — Cubic Time Complexity

This means the time grows proportionally to the cube of the input size.

🔸 Example:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            // constant-time operation
        }
    }
}

✅ This is n * n * n = n³

🔸 Where you see it:

• Matrix multiplication (naive approach)

• 3D dynamic programming problems

• Algorithms involving three nested loops on size n.

📊 Time Growth Comparison:

n	O(n)	O(n²)	O(n³)
10	10	100	1000
100	100	10,000	1,000,000
1000	1000	1,000,000	1,000,000,000

So, you can see that O(n²) and O(n³) become very slow for large inputs. That’s why we try to optimize!

🔷 O(2^x) — Exponential Time Complexity

🔹 Logic:

• For each of the x elements, you have 2 choices:

  • Include the element

  • Exclude the element

• So, total number of recursive paths = 2^x

🔸 Example Use Cases:

• Generating all subsets of an array

• Solving problems like 0/1 Knapsack (without optimization)

• Decision tree based recursion

---

🔷 O(n!) — Factorial Time Complexity

🔹 Logic:

• You're arranging n items in all possible ways

• For the first position, n choices

• For the second position, n-1 choices

• ...

• Total permutations = n!

🔸 Example Use Cases:

• Generating all permutations

• Traveling Salesman Problem (brute-force)

• Some backtracking problems with ordering (like solving puzzles or placing items in all ways)

---

📊 Time Growth Snapshot:

n	2ⁿ	n!
5	32	120
10	1024	3,628,800
20	1,048,57   6	2.43×10¹⁸

🔺 So we avoid these complexities for large n unless optimized using DP, pruning, or memoization.

---

🔷 What is Space Complexity?

Space Complexity is the total amount of memory used by an algorithm relative to the input size.

It includes:

1. Input space (sometimes ignored in analysis)

2. Auxiliary space — extra memory used during execution (like variables, arrays, stacks, recursion)

---

🔹 Why is it important?

• Helps us write memory-efficient code

• Useful in embedded systems, large-scale applications, and optimization tasks

---

🔸 Example 1: Constant Space O(1)

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += arr[i];
}

✅ Only one variable (sum), regardless of n ⇒ O(1) space

---

🔸 Example 2: Linear Space O(n)

vector<int> result;
for (int i = 0; i < n; i++) {
    result.push_back(arr[i] * 2);
}

✅ We use an extra array of size n ⇒ O(n) space

---

🔸 Example 3: Recursive Calls

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

✅ Recursive stack builds up to n calls ⇒ O(n) space

---

🧠 Quick Tips:

• Iterative approaches use less space than recursive ones (no stack)

• Use in-place techniques to save space (e.g., two-pointer, swapping)

• Watch out for hidden space in recursive solutions!

🚀Question to Solve

1. To Find time complexity of Prime Number

            for(int i=2; i*i<=n; i++){

                if(n%i= = 0){

                    count<<"Non Prime"<<count<<endl;

                    break;

           }

     }

Here is the explanation

                               i*i<=n       //i*i=(square of i)

                         i^2= n

                         i=√n

Time complexity of prime number is O(√n).

1. To Find time complexity of Selection sort

          for (int i = 0; i < n - 1; i++) {

        // Find the index of the minimum element in the unsorted part of the array

          int minIndex = i;

          for (int j = i + 1; j < n; j++) {

              if (arr[j] < arr[minIndex]) {

                  minIndex = j;

            }

        }

        // Swap the found minimum element with the element at index i

        if (minIndex != i) {

            swap(arr[i], arr[minIndex]);

        }

    }

    

📈 Practical Usage of Time Complexities

Input Size (n)	Time Complexity	Example
n > 10⁸	O(log n), O(1)	Efficient search, constant-time operations
n ≤ 10⁸	O(n)	Linear algorithms (e.g., traversing arrays)
n ≤ 10⁶	O(n log n)	Sorting algorithms (e.g., Merge Sort, Quick Sort)
n ≤ 10⁴	O(n²)	Brute-force methods (e.g., Bubble Sort, Selection Sort)
n ≤ 500	O(n³)	More complex algorithms (e.g., 3D matrix multiplication)
n ≤ 25	O(2ˣ)	Recursion, brute-force (e.g., subset generation)
n ≤ 12	O(n!)	Permutations, exhaustive search (e.g., Traveling Salesman Problem)

This structure will help your readers quickly understand the practical use cases of different time complexities depending on the input size.

🔚 Conclusion: Navigating the Complexity Jungle

Understanding time complexity is crucial for writing efficient algorithms and solving problems optimally. By mastering the different time complexities and their practical applications, you can:

• Choose the right algorithm for your problem, ensuring optimal performance.

• Avoid unnecessary inefficiencies, making your code scalable and future-proof.

• Balance time complexity with space complexity to craft efficient solutions that use minimal resources.

Remember, while big-O notation helps estimate an algorithm's efficiency, real-world factors like hardware, input patterns, and constraints should also guide your decision-making.

With the knowledge of time complexities, you are now equipped to tackle complex algorithms, optimize your solutions, and become a more efficient problem solver. Keep practicing, and over time, this will become second nature!

🙏 Thank You for Reading!

Thank you for taking the time to explore this blog and dive deep into the fascinating world of Time Complexity. I hope this guide has helped you understand the importance of algorithm efficiency and how it can transform the way you approach problem-solving.

Remember: Every programmer is on a journey, and the road to mastering algorithms and data structures takes persistence and practice. Keep learning, experimenting, and challenging yourself — each step brings you closer to becoming an exceptional coder.

Stay motivated, keep coding, and let your creativity and problem-solving skills guide you through every challenge.

Until next time, happy coding! 🚀😍