1/10
Flashcards about Algorithms and Complexity, focusing on Linear Search and Sigma Notation
Name | Mastery | Learn | Test | Matching | Spaced |
---|
No study sessions yet.
Sigma Notation
A mathematical shorthand for expressing sums where each term is of the same form.
Summation Formula for the sum of first N integers
∑_(i=1)^N i = 1 + 2 + 3 + … + N = (N(N+1))/2
Summation Formula for the sum of N ones
∑_(i=1)^N 1 = 1 + 1 + 1 + … + 1 = N
General Rule for the number of times the instruction within a for loop is executed (for (i = a; i <= b; i++))
b - a + 1
Worst-Case Analysis
Calculate the upper bound on the running time of an algorithm, knowing the case that causes a maximum number of operations to be executed.
Best-Case Analysis
Calculate the lower bound on the running time of an algorithm, knowing the case that causes a minimum number of operations to be executed.
Average-Case Analysis
Take all possible inputs and calculate the computing time for all of the inputs, then sum all the calculated values and divide the sum by the total number of inputs.
Best Case for Linear Search
The element being searched for is the first element in the array.
Worst Case for Linear Search
The element being searched for is not in the array.
Time complexity of Linear Search algorithm in Best Case
T(N) = Constant
Time complexity of Linear Search algorithm in Worst Case and Average Case
T(N) = C1 x N + C2, where C1 and C2 are constants.