Algorithm Analysis

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/18

flashcard set

Earn XP

Description and Tags

Flashcards for reviewing algorithm analysis concepts.

19 Terms

1
New cards

Algorithm

A procedure for accomplishing some tasks which, given an initial state, terminate in a defined end-state.

2
New cards
3
New cards
4
New cards

Space complexity

The amount of memory required by an algorithm to run to completion.

5
New cards
6
New cards

Time complexity

The amount of time it takes for an algorithm to run.

7
New cards

Fixed Part (Space Complexity)

The size required to store certain data/variables, that is independent of the size of the problem.

8
New cards

Variable Part (Space Complexity)

Space needed by variables, whose size is dependent on the size of the problem.

9
New cards

Define 'a' (Estimating Running Time)

The time taken by the fastest primitive operation.

10
New cards

Define 'b' (Estimating Running Time)

The time taken by the slowest primitive operation.

11
New cards

Pseudocode

High-level description of an algorithm; more structured than plain English, less detailed than a program.

12
New cards

Primitive Operations

Basic computations performed by an algorithm, largely independent from the programming language.

13
New cards

Big-Oh Notation

A notation that simplifies analysis by removing unneeded information, defining the upper bound of a function's growth rate.

14
New cards

Big Omega

Asymptotic lower bound.

15
New cards

Big Theta

Asymptotic tight bound.

16
New cards

ADT (Abstract Data Type)

A logical view of the data objects together with specifications of the operations required to create and manipulate them.

17
New cards

Representation(Data Type)

A specific encoding of an instance.

18
New cards

Opaque data types

data types in which the representation is not known to the user.

19
New cards

Transparent data types

data types in which the representation is profitably known to the user.