Time complexity

1. Linear Time Complexity - O(n)

Slide 1: What is Linear Time Complexity?

• Title: Understanding Linear Time Complexity

• Content:

  • Linear time complexity, written as O(n), means the time it takes for an algorithm to finish grows directly with the size of the input.

  • If the input size doubles, the time taken also doubles.

  • Simple Idea: More input, more time.

Slide 2: Example of O(n)

• Title: Simple Example of Linear Time Complexity

• Code:

    for (int i = 1; i <= n; i++) {
        System.out.println(i); // Runs n times
    }
  

• Explanation:

  • This loop prints numbers from 1 to n.

  • If n is 10, it prints 10 times. If n is 100, it prints 100 times.

  • Key Point: The bigger the input, the more times the loop runs.

Slide 3: When Do We See O(n)?

• Title: Common Situations for O(n)

• Content:

  • You see O(n) time complexity in tasks like:

    • Going through a list of items one by one.

    • Counting things.

    • Finding something by looking at each item.

  • Simple Idea: You do something to each item.

Slide 4: Why Does O(n) Matter?

• Title: Why Linear Time Complexity is Important

• Content:

  • O(n) is usually fast enough, but it can slow down with lots of data.

  • Example: If checking 1 million items takes 1 minute, checking 10 million items could take 10 minutes.

  • Simple Idea: Be careful with big data!

Slide 5: Quick Summary of O(n)

• Title: Wrapping Up Linear Time Complexity

• Content:

  • O(n) means time grows with input size.

  • Simple Advice: If your data is small, O(n) is usually fine. If it's big, think about ways to make it faster.

---

2. Constant Time Complexity - O(1)

Slide 1: What is Constant Time Complexity?

• Title: Understanding Constant Time Complexity

• Content:

  • Constant time complexity, written as O(1), means the time it takes doesn’t change with the size of the input.

  • The operation takes the same time no matter how much data you have.

  • Simple Idea: Always the same time.

Slide 2: Example of O(1)

• Title: Simple Example of Constant Time Complexity

• Code:

    int number = 10;
    System.out.println(number * 2); // Always takes the same amount of time
  

• Explanation:

  • Multiplying number by 2 and printing it takes the same time, no matter what number is.

  • Key Point: The size of the input doesn’t matter.

Slide 3: When Do We See O(1)?

• Title: Common Situations for O(1)

• Content:

  • You see O(1) time complexity in tasks like:

    • Checking a single item.

    • Doing simple math or logic.

    • Getting a specific piece of data.

  • Simple Idea: Quick and direct actions.

Slide 4: Why Does O(1) Matter?

• Title: Why Constant Time Complexity is Great

• Content:

  • O(1) is the fastest time complexity because it doesn’t get slower as data grows.

  • Example: Checking if a light is on or off takes the same time, no matter how many lights you have.

  • Simple Idea: Super fast and always predictable.

Slide 5: Quick Summary of O(1)

• Title: Wrapping Up Constant Time Complexity

• Content:

  • O(1) means the operation time is constant, no matter how much data you have.

  • Simple Advice: Always aim for O(1) if you can, especially in important parts of your code.

---

3. Quadratic Time Complexity - O(n²)

Slide 1: What is Quadratic Time Complexity?

• Title: Understanding Quadratic Time Complexity

• Content:

  • Quadratic time complexity, written as O(n²), means the time it takes grows as the square of the input size.

  • If the input size doubles, the time taken grows four times (because 2² = 4).

  • Simple Idea: Time grows really fast as data grows.

Slide 2: Example of O(n²)

• Title: Simple Example of Quadratic Time Complexity

• Code:

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            System.out.println(i + " " + j); // Runs n^2 times
        }
    }
  

• Explanation:

  • The first loop runs n times, and inside it, the second loop also runs n times.

  • This means the total work done is n * n or n².

  • Key Point: The time taken grows quickly as n increases.

Slide 3: When Do We See O(n²)?

• Title: Common Situations for O(n²)

• Content:

  • You see O(n²) time complexity in tasks like:

    • Comparing all pairs of items.

    • Simple sorting methods like bubble sort.

    • Generating combinations.

  • Simple Idea: Lots of pairwise comparisons.

Slide 4: Why Does O(n²) Matter?

• Title: Why Quadratic Time Can Be Slow

• Content:

  • O(n²) gets slow quickly as the amount of data grows.

  • Example: For 1000 items, the time is like doing 1,000,000 operations.

  • This can make programs very slow if not handled carefully.

  • Simple Idea: Be careful with O(n²) for big inputs.

Slide 5: Quick Summary of O(n²)

• Title: Wrapping Up Quadratic Time Complexity

• Content:

  • O(n²) means time grows much faster than the input size.

  • Simple Advice: If your data is small, O(n²) might be okay. For big data, look for ways to make your code faster.