Chapter 1 : What is an algorithm?

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

1/25

flashcard set

Earn XP

Description and Tags

Computer Engineering

University/Undergrad

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

26 Terms

1
New cards
Effectiveness
________ means that you can perform each operation precisely to solve the problem.
2
New cards
variable n
The ________ in an equation that describes the number of steps in an algorithm.
3
New cards
Definiteness
________ means that the steps are clear, concise, and unambiguous.
4
New cards
finite process
He (Donald Knuths) describes an algorithm as a definite, effective, and ________ that receives input and produces output based on this input.
5
New cards
Finiteness
________ means that the algorithm stops after a finite number of steps.
6
New cards
amount of memory a program
The ________ requires to store the data set.
7
New cards
Time complexity
________ is the maximum number of steps an algorithm takes to complete as n gets larger.
8
New cards
Temporary space
________ is the amount of memory your algorithm needs for intermediary processing, for example, if your algorithm needs to temporarily copy a list to transfer data.
9
New cards
big O notation
The ________ for exponential complexity is O (c** n), where c is a constant.
10
New cards
worst possible scenario
An algorithms best- case complexity is how it performs with ideal input, and an algorithms worst- case complexity is how it performs in the ________ for it.
11
New cards
Linear Time
________: The next most efficient type of algorithm is one that runs in ________.
12
New cards
Exponential scaling
________ is the reason why it is so important to create long passwords.
13
New cards
order of magnitude
A(n) ________ is a class in a classification system where each class is many times greater or smaller than the one before.
14
New cards
brute force algorithm
A(n) ________ is a type of algorithm that tests every possible option.
15
New cards
Constant Time
________: The most efficient order of magnitude is called constant time complexity.
16
New cards
amount of memory an algorithm
The ________ needs for intermediary processing, for example, if your algorithm needs to temporarily copy a list to transfer data.
17
New cards
amount of time it
The ________ takes a computer to execute an algorithm written in a programming language.
18
New cards
Big O notation
________ is a mathematical notation that describes how an algorithms time or space requirements (you will learn about space requirements later) increase as the size of n increases.
19
New cards
linear time
An algorithm runs in ________ when it grows at the same rate as the problems size.
20
New cards
big O notation
Computer scientists use ________ to create an order- of- magnitude function from T (n)
21
New cards
Constant Time
The most efficient order of magnitude is called constant time complexity
22
New cards
Logarithmic Time
Logarithmic time is the second most efficient time complexity
23
New cards
Linear Time
The next most efficient type of algorithm is one that runs in linear time
24
New cards
Log-Linear Time
An algorithm that runs in log-linear time grows as a combination (multiplication) of logarithmic and linear time complexities
25
New cards
Quadratic Time
After log-linear, the next most efficient time complexity is quadratic time
26
New cards
Cubic Time
After quadratic comes cubic time complexity