??Time complexity

Understanding Time Complexity in Algorithms

Time complexity is a critical concept in computer science that measures the amount of time an algorithm takes to complete as a function of the length of the input. It provides a way to evaluate the efficiency of an algorithm and predict its performance, which is essential for writing optimized code.

What is Time Complexity?

Time complexity gives us an idea of the number of operations an algorithm will perform relative to the size of its input. It helps in understanding how an algorithm's running time grows with the input size, allowing developers to make informed decisions about which algorithm to use in different scenarios.

How to Represent Time Complexity?

Time complexity is typically represented using Big O notation, which describes the upper bound of an algorithm's running time. It provides an asymptotic analysis of the algorithm's performance, focusing on the term that grows the fastest as the input size increases.

What is Big O Notation?

Big O notation is a mathematical notation used to describe the upper limit of an algorithm's running time. It characterizes algorithms based on their worst-case or upper bound performance, providing a high-level understanding of their efficiency.

O(1) - Constant Time

• Description: The running time of the algorithm is constant, regardless of the input size. It performs a fixed number of operations.

O(log n) - Logarithmic Time

• Description: The running time grows logarithmically as the input size increases. This often occurs in algorithms that repeatedly divide the input in half.

O(n) - Linear Time

• Description: The running time grows linearly with the input size. Each additional element in the input increases the running time proportionally.

O(n^2) - Quadratic Time

• Description: The running time grows quadratically with the input size. This often occurs in algorithms with nested loops.

Best Case, Worst Case, and Average Case

When analyzing an algorithm, it's important to consider different scenarios:

1. ??Best Case: The scenario where the algorithm performs the fewest operations. For example, in a linear search, the best case is O(1) when the target element is the first element in the array.
2. ??Worst Case: The scenario where the algorithm performs the most operations. In a linear search, the worst case is O(n) when the target element is the last element or not present in the array.
3. ???Average Case: The expected scenario where the algorithm performs a moderate number of operations. It provides a more realistic measure of an algorithm's performance in typical use.

Example:

public class StudentMarksCheck {
    public static void main(String[] args) {
        int[] marks = {85, 92, 76, 64, 89, 99, 75, 63, 91, 80};
        int targetMarkBestCase = 85;  
        int targetMarkWorstCase = 80; 
        int targetMarkAverageCase = 89; 

        System.out.println("Best Case:");
        checkMark(marks, targetMarkBestCase);

        System.out.println("Worst Case:");
        checkMark(marks, targetMarkWorstCase);

        System.out.println("Average Case:");
        checkMark(marks, targetMarkAverageCase);
    }

    public static void checkMark(int[] marks, int target) {
        for (int i = 0; i < marks.length; i++) {
            if (marks[i] == target) {
                System.out.println("Mark " + target + " found at index " + i);
                return;
            }
        }
        System.out.println("Mark " + target + " not found.");
    }
}        

Best case

Input: Target mark is the first element (85).

Output: The algorithm finds the target immediately.

Time Complexity: O(1)

Worst case

Input: Target mark is the last element (80).

Output: The algorithm checks every element until the last one.

Time Complexity: O(n)

Average case

Input: Target mark is somewhere in the middle (89).

Output: The algorithm checks approximately half of the elements.

Time Complexity: O(n)

Output

Best Case:
Mark 85 found at index 0

Worst Case:
Mark 80 found at index 9

Average Case:
Mark 89 found at index 4