## Notes Represents the average time complexity of an algorithm by describing both the upper and lower asymptotic bounds. ## Example 1: Linear Search Given an array, estimate the Big Theta of finding a given value using [[Linear Search]]. - The time complexity is O(n) - The space complexity is O(1) because we need a constant number of variables to store the comparison values ### Calculate Average Time Complexity ```math average time complexity = SUM(big_theta(i))/(n+1), where i is 1, 2, 3, ..., n, and not present average time complexity = big_theta((n+1)*(n+2)/2)/(n+1) average time complexity = big_theta(1 + n/2), because the "(n+1)" terms cancel out average time complexity = big_theta(n) ```