Unit 1 Flashcards
To determine the best algorithms to use, computer scientists analyze the complexity of the algorithm by comparing two algorithms at the blank level
idea
To analyze algorithm complexity, computer scientists use pragmatic tools such as blank, blank and blank notations to formally measure how fast a program or algorithm runs.
big-O, Theta, and Omega
An blank is a step-by-step method for solving a problem. A description of an algorithm specifies the input to the problem, the output to the problem, and the sequence of steps to be followed to obtain the output from the input.
algorithm
Algorithms are often described in blank, which is a detailed yet readable description of what an algorithm must do, expressed in a formally-styled natural language rather than in a programming language.
pseudocode
An important type of step in an algorithm is an blank, in which a variable is given a value.
assignment
An assignment operator is denoted by:
blank
x := y
The output of an algorithm is specified by a blank statement.
return
A description of an algorithm starts with the blank.
name of the algorithm
The name is followed by a blank of what the algorithm computes
description
A description of an algorithm usually includes what five steps:
A name for the algorithm
A brief description of the task performed by the algorithm
A description of the input
A description of the output
A sequence of steps to follow
An blank tests a condition, and executes one or more instructions if the condition evaluates to true.
if-statement
In a blank, a condition and instruction appear on the same line.
single line if-statement
What is the notation for an if-statement?
If (x = 5), y := 7
An if-statement can also be followed by a blank of indented operations with a final end-if statement.
If ( condition )
Step 1
Step 2
. . .
Step n
End-if
sequence
An blank tests a condition, executes one or more instructions if the condition evaluates to true, and executes a different set of instructions if the condition evaluates to false
if-else-statement
Name the pattern for if-else statement
If ( condition )
One or more steps
Else
One or more steps
End-if
An if-then statement tests a blank and executes one or more steps if the condition is true. An if-else statement tests the condition, and executes one or more instructions if the condition is true, and another instruction or set of instructions if it is false.
condition
The structure of the if-then statement in pseudocode when there is only one step to execute when the condition is true is:
blank
If(condition), step
When multiple steps should be performed upon a true condition, the steps are indented and the end of the list of steps is noted with an blank statement:
End-if
The if-else statement in pseudocode is formatted in what format:
If (condition)
One or more steps
Else
One or more steps
End-if
The multiple step if statement in pseudocode is formatted in what format:
If (condition)
Step 1
Step 2
…
Step n
End-if
When needed, if-then and if-else statements can be blank
nested.
There are blank regarding how many if-then or if-else statements can be placed under another if-then or if-else statement.
no limitations
An blank is a process where a set of instructions or structures are repeated in a sequence a specified number of times or until a condition is met.
iteration
To control the iterations, blank use an index or a counter and a variable that counts how many times a step or a block of steps executes.
for-loops
Blank structures provide a means of specifying a sequence of steps that are to be repeated.
Looping
There are two common types of loops: blank and blank.
for-loops and while-loops
In a blank, a block of instructions is executed a fixed number of times as specified in the first line of the for-loop, which defines an index, a starting value for the index, and a final value for the index.
for-loop
Each repetition of the block of instructions inside the for-loop is called an blank
iteration.
The index is initially assigned a value equal to the blank, and is incremented just before the next iteration begins. The final iteration of the for-loop happens when the index reaches the final value.
starting value
Give the syntax for a for loop
For i = s to t
Step 1
Step 2
. . .
Step n
End-for
For-loops are used when the number of iterations in the loop is blank.
known
The for-loop iterates blank times.
final_value-start_value+1
A blank iterates an unknown number of times, ending when a certain condition becomes false.
while-loop
A while-loop is written as blank:
While ( condition )
Step 1
Step 2
. . .
Step n
End-while
The blank is an expression that evaluates to true or false. If the expression evaluates to true, then steps 1 through n are performed and the algorithm goes back to the first statement where the condition is re-evaluated. The process continues until the condition evaluates to false, at which point the algorithm proceeds with the next step after the while-loop.
condition
blank are used when the number of iterations in the loop is unknown and may execute zero or more iterations.
While-loops
While loops are controlled by a blank. If the blank is true, the loop initiates an iteration otherwise it stops.
conditional statement
While-loops use the blank syntax in pseudocode:
While (condition)
One or more steps
End-while
The while-loop iterates blank or blank times until the condition is met.
zero or more
When a loop exists within another loop, it is called a blank loop
nested
When loops are nested the blank loop takes control of the number of complete repetitions of the blank loop.
outer
inner
A blank is a loop that appears within another loop
nested loop
The nested loop, known as the blank, is treated as a sequence of steps inside the outer loop.
inner loop
blank can nest in blank, and vice-versa; loops of the same type can also nest.
While-loops
for-loops
The blank takes control of the number of complete repetitions of the blank.
The first pass of the outer loop triggers the inner loop, which executes to completion.
Then the second pass of the outer loop triggers the inner loop again.
This repeats until the outer loop finishes.
outer loop
inner loop
To solve a problem an algorithm needs blank
resources
The primary resources to optimize are blank, the time the algorithm requires to run, and blank, the amount of memory used.
time complexity
space complexity
The blank depends on the speed of the processing unit, the number of calculations that need to be performed, the number of conditions that need to be evaluated, or the number of iterations to be completed by the loops.
time
The values of all variables, including the values of the input variables and all other values that will be computed, need to be stored somewhere in the blank of the system—in the RAM, hard drive, or external devices.
memory
Naturally, a program will take more time and space on larger inputs. For example, a program that sorts a sequence of numbers will take a longer time to sort a long sequence than a short sequence. Therefore, time and space efficiency are measured in terms of the blank
input size
The way the size of the input is measured varies based on the blank
type of problem
When sorting numbers, for example, the blank is the number of numbers to be sorted.
input size
An algorithm that processes a digital image would likely be measured as a function of the blank in the image.
number of pixels
An algorithm that processes a recorded speech given at a commencement ceremony will likely use the blank as the size of the input.
length of the speech
The input size for a problem is usually denoted by the variable blank
, and the assessments of the algorithms’ resources needs are denoted in functions of blank that give the best-, worst-, and average-case scenario behavior of the algorithms.
n
Not all elements of the blank provide equally relevant information about how much more resources an algorithm would need as n grows.
complexity functions
What is
F[1] :=1
F[2]:=1
For i:=3 to n
F[i] := F[i-1]+F[i- 2]
End-for
Return (F[n])
Algorithm Fibonacci-1
The choice of blank can heavily influence the efficiency of a solution to a computing problem
algorithms
Blank is a measure of the resources an algorithm uses.
Computational complexity
blank measures the time an algorithm needs to complete.
Time complexity
Blank measures the amount of memory an algorithm uses during its execution
Space complexity
Programmers commonly seek optimal ways to sort numbers and optimize databases to store data with algorithms that will speed up blank
retrieval
These operations (e.g., addition, multiplication, comparison) that one would find in a single line of pseudocode, are referred to as blank
atomic operations
They are called “atomic,” because they cannot be split any further; a computer would evaluate each in one step.
blank takes longer to complete than addition, as multiple additions need to happen to find the product of two numbers.
Multiplication
blank is the same as the addition of negated numbers and division is a series of subtractions.
Subtraction
Blank is a repeated multiplication, so it takes longer to execute
Exponentiation
At the same time, a blank takes longer to complete than assignments, as they consist of statements that are integrated multiple times.
loop
As the size of the input grows, blank and blank partake less and less in the total time the algorithm takes to complete because the multiplication and loops dominate the time.
addition and assignment statements
Each blank has its position in the sequence, and the total number of blank in the sequence is referred to as its size.
element
Use these guidelines to count the number of atomic operations:
Count each assignment as one operation
Multiply the operations in the body of the loop by the number of iterations of the loop
Ignore constant factors; focus on the elements of the functions that grow the fastest
Specific features of computing systems, such as blank, are not considered when comparing how the time to complete an algorithm grows as the size of the input grows.
processor speed
blank is performed to measure the resources (time or space) that an algorithm requires in the worst case.
Worst-case analysis
The term “worst case” refers to an input that triggers the blank of calculations, thus taking the longest to complete of all other inputs of the same size
maximum number
The worst-case analysis provides an blank on the resources required by the algorithm.
upper bound
blank are compared by their average running and best running times.
Algorithms
blank is used to estimate how much time might be needed in the worst case to guarantee that the algorithm will always finish on time.
Worst-case complexity
blank and blank are the most used in algorithm analysis.
Average performance and worst-case performance
the behavior of the complexity function as n grows.
asymptotic complexity
Any program that doesn’t have loops will have an asymptotic complexity of blank, since the number of instructions it needs is just a constant.
1
Any program with a single loop which goes from 1 to n will have asymptotic complexity blank since it will do a constant number of instructions before the loop, a constant number of instructions after the loop, and a constant number of instructions within the loop which all run n times.
n,
This method of searching for a value within an array is called blank. The asymptotic complexity for this algorithm is n due to the single for-loop. Note that this algorithm might not need to go through all n elements of the array to find one; however, in the worst-case scenario when it does (when no elements equals V or the last element of the array equals V), the loop will run n times.
linear search.
Simple programs can be analyzed by counting the blank of the program.
A single loop over n items yields asymptotic complexity n.
nested loops
If you have a program that calls a function within a loop and you know the number of atomic operations the called function performs, it is easy to determine the blank of the whole program.
number of atomic operations
Since you know that f(n) is a function that performs exactly n instructions, you then know that the number of instructions of the whole program is asymptotically blank, as the function is called exactly n times.
n2
Given a series of for-loops that are sequential, the blank of them determines the asymptotic behavior of the program.
slowest
blank is a basic mathematical tool for working with functions that we only know up to a constant factor. There are three types of asymptotic notation that are commonly used in algorithmic analysis, O(n) (“big-O”), Ω(n) (“Omega”), and Θ(n) (“Theta”).
Asymptotic notation
Two nested loops followed by a single loop is asymptotically blank as the nested loops alone, because the nested loops dominate the simple loop.
the same
Blank—serves as a rough upper bound for functions (disregarding constants and small input values).
The big-O notation—O(n)
The blank is similar to big-O, except that it provides a lower bound on the growth of a function.
Ω notation—Ω(n)—
The blank—indicates how the algorithm performs for any case. This is referred to as an average time or random case function and, when possible, gives us a sense of how the algorithm performs in any case. Note that it is often possible to estimate upper and lower bounds, but not average cases especially if there are complex branching in the code.
Θ notation—Θ(n)
Blank describes the behavior of the complexity function as n grows. Only the terms that grow fastest in a complexity function significantly influences its blank, so they are retained without constant multipliers.
Asymptotic complexity
To find the asymptotic behavior for the given function, drop the constant factors and keep the terms that blank. For example, in this function: 6n + 4, drop the 4 because it remains constant and the constant multiplier 6.
grow the fastest
An algorithm without loops has a constant asymptotic complexity of blank, since the number of instructions it needs is just a constant.
1
Any program with a single loop which goes from 1 to n will have asymptotic complexity blank, since it will do a constant number of instructions before the loop, a constant number of instructions after the loop, and a constant number of instructions within the loop which all run n times.
n
If you cannot readily decide which one of the terms grows faster, plug in several large values for blank and compare.
n
A single loop that iterates up to n times has a blank asymptotic complexity.
linear
The asymptotic complexity of a loop nested in a loop is blank.
quadratic
The blank is the most common in the context running times/time complexity.
big-O notation
The functions f(n) and g(n) are called upper and lower bounds of the asymptotic complexity of the algorithm and the following is true by definition:
Ω(f(n)) ≤ Θ(f(n)) ≤ O(f(n)).
blank, blank and blank are formal notational methods for stating the growth of resource needs (time and storage) of an algorithm.
Big-O, Omega, and Theta
The function that counts the atomic operations of an algorithm falls under the blank.
big-O function
The function that counts the atomic operations of an algorithm is above blank.
the Omega function
The blank falls between the big-O and Omega functions.
Theta function
