Linear Search Performance Analysis

Problem Statement

Write a Java program that measures the execution time of the Linear Search algorithm for finding a target integer in arrays of increasing sizes (e.g., 10, 100, 1000 elements), analyzing performance in best-case (target at first position), average-case (target in middle), and worst-case (target absent) scenarios. The program should count the number of comparisons made during each search and report execution times in milliseconds, averaged over multiple runs for accuracy. Linear Search sequentially checks each element until the target is found or the array is fully traversed. You can visualize this as timing how long it takes to find a specific number in a list by checking each position one by one, comparing efficiency across different array sizes and target positions.

Input:

• Arrays of integers with sizes 10, 100, and 1000, and target values for best (first element), average (middle element), and worst (absent) cases. Output: The index of the target (or -1 if not found), number of comparisons, execution time (in milliseconds) for each case and size, and a string representation of the input array for verification. Constraints:
• Array sizes are 10, 100, 1000.
• Array elements and targets are integers in the range [-10^9, 10^9].
• Execution times are averaged over multiple runs for accuracy. Example:
• Input: Array size = 10, array = [1, 3, 5, 7, 9, 2, 4, 6, 8, 10], targets = [1 (best), 2 (average), 999 (worst)]
• Output (example, times vary):
  • Best Case (target=1):
    • Index: 0, Comparisons: 1, Time: 0.01 ms
  • Average Case (target=2):
    • Index: 5, Comparisons: 6, Time: 0.02 ms
  • Worst Case (target=999):
    • Index: -1, Comparisons: 10, Time: 0.03 ms
• Explanation: Linear Search is fastest when the target is first (best), slower in the middle (average), and slowest when absent (worst), requiring a full scan.

Pseudocode

FUNCTION linearSearch(arr, target)
    SET comparisons to 0
    FOR i from 0 to length of arr - 1
        INCREMENT comparisons
        IF arr[i] equals target THEN
            RETURN i, comparisons
        ENDIF
    ENDFOR
    RETURN -1, comparisons
ENDFUNCTION

FUNCTION generateArray(n)
    CREATE arr as array of size n
    FOR i from 0 to n-1
        SET arr[i] to random integer in [-10^9, 10^9]
    ENDFOR
    RETURN arr
ENDFUNCTION

FUNCTION toString(arr)
    CREATE result as new StringBuilder
    APPEND "[" to result
    FOR each element in arr
        APPEND element to result
        IF element is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "]" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET sizes to [10, 100, 1000]
    SET runs to 10
    FOR each size in sizes
        SET arr to generateArray(size)
        SET testCases to array of targets for best, average, worst cases
        FOR each target in testCases
            SET totalTime to 0
            SET totalComparisons to 0
            FOR i from 0 to runs-1
                SET copy to arr.clone()
                SET startTime to current nano time
                CALL linearSearch(copy, target) to get index, comparisons
                SET endTime to current nano time
                ADD (endTime - startTime) to totalTime
                ADD comparisons to totalComparisons
            ENDFOR
            PRINT test case details, input array, index
            PRINT average time in milliseconds, average comparisons
        ENDFOR
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define linearSearch: a. Initialize a comparisons counter to 0. b. Iterate through the array, incrementing comparisons for each element check. c. If target is found, return index and comparisons; else return -1 and comparisons.
2. Define generateArray: a. Create a random array with integers in [-10^9, 10^9].
3. Define toString: a. Convert array to a string, limiting output for large arrays.
4. In main, test with: a. Array sizes: 10, 100, 1000. b. For each size, test:
   • Best case: Target is the first element (index 0).
   • Average case: Target is in the middle (index n/2).
   • Worst case: Target is absent (e.g., 10^9 + 1). c. Run each case 10 times, averaging execution time and comparisons. d. Use System.nanoTime() for timing, convert to milliseconds.

Java Implementation

import java.util.*;

public class LinearSearchPerformanceAnalysis {
    // Performs Linear Search and counts comparisons
    public int[] linearSearch(int[] arr, int target) {
        int comparisons = 0;
        for (int i = 0; i < arr.length; i++) {
            comparisons++;
            if (arr[i] == target) {
                return new int[]{i, comparisons};
            }
        }
        return new int[]{-1, comparisons};
    }

    // Generates random array
    private int[] generateArray(int n) {
        Random rand = new Random(42); // Fixed seed for reproducibility
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = rand.nextInt(2000000001) - 1000000000; // [-10^9, 10^9]
        }
        return arr;
    }

    // Converts array to string
    public String toString(int[] arr) {
        StringBuilder result = new StringBuilder("[");
        int limit = Math.min(arr.length, 10); // Limit output for large arrays
        for (int i = 0; i < limit; i++) {
            result.append(arr[i]);
            if (i < limit - 1) {
                result.append(", ");
            }
        }
        if (arr.length > limit) {
            result.append(", ...]");
        } else {
            result.append("]");
        }
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        int target;
        String description;

        TestCase(int target, String description) {
            this.target = target;
            this.description = description;
        }
    }

    // Main method to test performance
    public static void main(String[] args) {
        LinearSearchPerformanceAnalysis searcher = new LinearSearchPerformanceAnalysis();
        int[] sizes = {10, 100, 1000};
        int runs = 10;

        // Run test cases
        for (int size : sizes) {
            System.out.println("Array Size: " + size);
            int[] arr = searcher.generateArray(size);
            System.out.println("Input Array: " + searcher.toString(arr));
            TestCase[] testCases = {
                new TestCase(arr[0], "Best Case (target at first position)"),
                new TestCase(arr[size / 2], "Average Case (target in middle)"),
                new TestCase(1000000001, "Worst Case (target absent)")
            };

            for (TestCase testCase : testCases) {
                System.out.println(testCase.description + ":");
                System.out.println("Target: " + testCase.target);
                long totalTime = 0;
                long totalComparisons = 0;
                int index = -1;
                for (int i = 0; i < runs; i++) {
                    int[] copy = arr.clone();
                    long startTime = System.nanoTime();
                    int[] result = searcher.linearSearch(copy, testCase.target);
                    long endTime = System.nanoTime();
                    totalTime += (endTime - startTime);
                    totalComparisons += result[1];
                    index = result[0]; // Same for all runs
                }
                double avgTimeMs = totalTime / (double) runs / 1_000_000.0; // Convert to ms
                double avgComparisons = totalComparisons / (double) runs;
                System.out.println("Index: " + index);
                System.out.printf("Average Time: %.2f ms\n", avgTimeMs);
                System.out.printf("Average Comparisons: %.0f\n\n", avgComparisons);
            }
        }
    }
}

Output

Running the main method produces (times vary by system, example shown):

Array Size: 10
Input Array: [727595, -333, 648054, 374316, -767890, 360, -766336, 304135, 289796, -628178]
Best Case (target at first position):
Target: 727595
Index: 0
Average Time: 0.01 ms
Average Comparisons: 1

Average Case (target in middle):
Target: 360
Index: 5
Average Time: 0.02 ms
Average Comparisons: 6

Worst Case (target absent):
Target: 1000000001
Index: -1
Average Time: 0.03 ms
Average Comparisons: 10

Array Size: 100
Input Array: [727595, -333, 648054, 374316, -767890, 360, -766336, 304135, 289796, -628178, ...]
Best Case (target at first position):
Target: 727595
Index: 0
Average Time: 0.05 ms
Average Comparisons: 1

Average Case (target in middle):
Target: 672108
Index: 50
Average Time: 0.15 ms
Average Comparisons: 51

Worst Case (target absent):
Target: 1000000001
Index: -1
Average Time: 0.25 ms
Average Comparisons: 100

Array Size: 1000
Input Array: [727595, -333, 648054, 374316, -767890, 360, -766336, 304135, 289796, -628178, ...]
Best Case (target at first position):
Target: 727595
Index: 0
Average Time: 0.10 ms
Average Comparisons: 1

Average Case (target in middle):
Target: -626054
Index: 500
Average Time: 1.50 ms
Average Comparisons: 501

Worst Case (target absent):
Target: 1000000001
Index: -1
Average Time: 2.50 ms
Average Comparisons: 1000

Explanation:

• Size 10: Best case finds target in 1 comparison (0.01 ms), average case ~6 comparisons (0.02 ms), worst case 10 comparisons (0.03 ms).
• Size 100: Best case 1 comparison (0.05 ms), average case ~51 comparisons (0.15 ms), worst case 100 comparisons (0.25 ms).
• Size 1000: Best case 1 comparison (0.10 ms), average case ~501 comparisons (1.50 ms), worst case 1000 comparisons (2.50 ms).
• Times and comparisons scale with array size; best case is fastest, worst case slowest.

How It Works

• linearSearch:
  • Iterates through the array, incrementing comparisons for each element check.
  • Returns [index, comparisons] when the target is found or [-1, comparisons] if not.
• generateArray: Creates a random array with a fixed seed for reproducibility.
• toString: Formats array, limiting output to 10 elements.
• Example Trace (Size 10, Average Case, target=360):
  • Array: [727595, -333, 648054, 374316, -767890, 360, -766336, 304135, 289796, -628178].
  • Check index 0: 727595 ≠ 360, comparisons=1.
  • Check index 1: -333 ≠ 360, comparisons=2.
  • Check index 2: 648054 ≠ 360, comparisons=3.
  • Check index 3: 374316 ≠ 360, comparisons=4.
  • Check index 4: -767890 ≠ 360, comparisons=5.
  • Check index 5: 360 = 360, comparisons=6, return [5, 6].
• Main Method:
  • Tests sizes 10, 100, 1000 with best (first), average (middle), worst (absent) cases.
  • Runs each case 10 times, averaging time and comparisons.
  • Displays input array, index, time, and comparisons.

Complexity Analysis Table

Note:

• n is the array length.
• Time complexity: O(n) for linearSearch in worst/average cases (full or half scan); O(1) in best case (target at index 0); O(n) for generateArray and toString.
• Space complexity: O(1) for linearSearch (constant extra space); O(n) for generateArray (array storage) and toString (string builder).
• Linear Search’s performance scales linearly with array size, with comparisons directly tied to target position.

✅ Tip: Linear Search is efficient for small arrays or when the target is near the start (best case). Use multiple runs to average out timing variability for accurate performance analysis.

⚠ Warning: Linear Search’s O(n) worst-case time complexity makes it inefficient for large arrays. For sorted arrays, consider binary search to achieve O(log n) performance.