Asymptotic Notations:

• There are a lot of standard units to represent and compare quantities.
• For example:
  • Distance Measurement → Kilometers (km), Meters (m), Centimeters (cm)
  • Storage Measurement → Kilobytes (KB), Megabytes (MB), Gigabytes (GB)
  • Blood Groups → A+, A-, B+, B-, O+, O-
  • Temperature Measurement → Celsius (°C), Fahrenheit (°F), Kelvin (K)
• Similarly, Asymptotic notations are mathematical tools used to represent or describe the time and space complexity of an algorithm in terms of input size (n).
• There are total 5 types of asymptotic notations:
  1. Big O (O)
     • Big O describes the maximum time or space an algorithm can take for large input.
     • It represents an upper bound on growth.
     • It is commonly used for the worst case, but in theory it can describe any upper limit.
  2. Big Omega (Ω)
     • Big Omega describes the minimum time or space an algorithm will take for large input.
     • It represents a lower bound on growth.
     • It is sometimes shown as the best case, but technically it just means any lower limit.
  3. Big Theta (Θ)
     • Big Theta describes the exact growth rate of an algorithm because it is bounded both above and below.
     • It represents a tight bound.
     • It shows the typical or exact growth and is not tied to best or worst case.
  4. Little o (o)
     • Little o describes functions that grow strictly slower than another function, but never equal.
     • It represents a strictly smaller upper bound.
     • It is not related to best, worst, or average case—only to strict growth comparison.
  5. Little Omega (ω)
     • Little omega describes functions that grow strictly faster than another function, but never equal.
     • It represents a strictly bigger lower bound.
     • It is not related to best, worst, or average case—only to strict growth comparison.
NOTE : We mostly use Big O Notation (O) to analyze algorithms because:
• A student is :
  • Good in Physics
  • Average in Maths
  • Worst in Chemestry
  Then student should focus on chemestry to improve overall performance and not get failed in exams.
• Similarly, we should focus on the worst-case scenario of an algorithm so that our algorithm does not fail in any situation.
• Asymptotic Notations give a high-level, machine-independent way to analyze algorithm efficiency.
• Instead of actual execution time or memory in MB, they focus on how these values change as input grows.

Programming Examples :

• Program 1 : (Traverse an Array)

  • import java.util.Scanner;
    
    public class ArrayTraversal
    {
        public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);
    
            // Input size of the array
            System.out.print("Enter number of elements: ");
            int n = sc.nextInt();
    
            int[] arr = new int[n];
    
            // Input elements
            System.out.println("Enter " + n + " elements:");
            for (int i = 0; i < n; i++)
            {
                arr[i] = sc.nextInt();
            }
    
            // Traverse and print elements
            System.out.println("Traversing the array:");
            for (int i = 0; i < n; i++)
            {
                System.out.println(arr[i]);
            }
        }
    }

  • Case	Description	Complexity
    Worst Case	Even in the worst case, we visit every element once, so complexity is O(n).	O(n)
    Average Case	On average, we visit all elements once, so complexity is Θ(n).	Θ(n)
    Best Case	We still need to visit every element once, so complexity is Ω(n).	Ω(n)

• Program 2 : (Linear Search in Array)

  • import java.util.Scanner;
    
    public class LinearSearch
    {
        public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);
    
            // Input size of the array
            System.out.print("Enter number of elements: ");
            int n = sc.nextInt();
    
            int[] arr = new int[n];
    
            // Input elements
            System.out.println("Enter " + n + " elements:");
            for (int i = 0; i < n; i++)
            {
                arr[i] = sc.nextInt();
            }
    
            // Input element to search
            System.out.print("Enter element to search: ");
            int key = sc.nextInt();
    
            // Linear search
            boolean found = false;
            for (int i = 0; i < n; i++)
            {
                if (arr[i] == key)
                {
                    System.out.println("Element found at index: " + i);
                    found = true;
                    break;
                }
            }
    
            if (!found)
            {
                System.out.println("Element not found in the array.");
            }
        }
    }

  • Case	Description	Complexity
    Worst Case	The element is either at the last position or not present at all, requiring n comparisons.	O(n)
    Average Case	The element is found somewhere in the middle of the array, so we make about n/2 comparisons on average.	Θ(n)
    Best Case	The element is found at the first position, so only one comparison is needed.	Ω(1)