Algorithms and Complexity Analysis

Flashcards covering key concepts of algorithms and complexity analysis.

An algorithm can be defined as a finite set of __ that can be followed to solve a particular problem.

step-by-step procedures/instructions

An algorithm must always terminate after a finite number of __.

steps

Each step of an algorithm must be __ defined; the actions to be carried out must be rigorously specified.

precisely

An algorithm can have zero or more __ which are quantities given to it initially.

inputs

An algorithm must produce one or more __ that have a specified relation to the inputs.

outputs

Effectiveness means that all operations to be performed in the algorithm must be __ and can be done in a finite length of time.

basic

An algorithm must be __ so that each instruction can be carried out.

feasible/practical/doable

An algorithm must be __ independent, meaning it can be implemented using any programming language without changing the output.

language

Algorithms are used to solve problems in areas ranging from simple sorting to and .

artificial intelligence; machine learning

There are two major types of algorithms based on their implementation method: and .

iterative; recursive

In iterative algorithms, functions run repeatedly until a __ is met or it fails.

condition

Recursive algorithms work by repeatedly __ themselves with a smaller input until a base condition is reached.

calling

The method __ breaks down a problem into smaller, independent subproblems, recursively solves them, and combines their solutions.

Divide and Conquer

Dynamic programming is used when subproblems __, storing results to avoid redundant computations.

overlap

Greedy algorithms make locally optimal choices at each step with the hope of finding a __ optimal solution.

globally

Algorithm analysis is the theoretical study of a computer program's and usage.

performance; resource

The analysis of an algorithm helps to determine the best algorithm concerning performance and __ usage.

resource

Practical analysis of algorithms can be done either or .

priori; posteriori

Time complexity deals with the amount of __ needed by an algorithm to run to completion.

time

Space complexity is defined as the amount of __ required by an algorithm to run to completion.

memory

The __ case time complexity refers to the maximum amount of time taken by an algorithm to complete its execution.

worst-case

The __ case complexity provides the average amount of time needed for an algorithm to execute.

average-case

Linear search has a time complexity of O(n), while binary search has a time complexity of __.

O(log n)