Algorithms and Complexity: Linear Search Time Complexity

0.0(0)
studied byStudied by 0 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/10

flashcard set

Earn XP

Description and Tags

Flashcards about Algorithms and Complexity, focusing on Linear Search and Sigma Notation

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

11 Terms

1
New cards

Sigma Notation

A mathematical shorthand for expressing sums where each term is of the same form.

2
New cards

Summation Formula for the sum of first N integers

∑_(i=1)^N i = 1 + 2 + 3 + … + N = (N(N+1))/2

3
New cards

Summation Formula for the sum of N ones

∑_(i=1)^N 1 = 1 + 1 + 1 + … + 1 = N

4
New cards

General Rule for the number of times the instruction within a for loop is executed (for (i = a; i <= b; i++))

b - a + 1

5
New cards

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.

6
New cards

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.

7
New cards

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.

8
New cards

Best Case for Linear Search

The element being searched for is the first element in the array.

9
New cards

Worst Case for Linear Search

The element being searched for is not in the array.

10
New cards

Time complexity of Linear Search algorithm in Best Case

T(N) = Constant

11
New cards

Time complexity of Linear Search algorithm in Worst Case and Average Case

T(N) = C1 x N + C2, where C1 and C2 are constants.