Design and Analysis of Algorithms - Comprehensive Review

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

1/10

encourage image

There's no tags or description

Looks like no tags are added yet.

11 Terms

1
New cards

Algorithm

A step-by-step procedure for performing some task in a finite amount of time.

2
New cards
3
New cards

Data Structure

A systematic way of organizing and accessing data.

4
New cards

Primitive Operation

A basic computation performed by an algorithm—such as evaluating an expression, assigning a value, comparing two numbers, indexing into an array, calling a method, or returning from a method—assumed to execute in a constant amount of time in the RAM model.

5
New cards

Space Complexity

A measure of the total working storage memory required by an algorithm, represented by the formula S(P)=C+S(instance)S(P) = C + S(\text{instance}).

6
New cards

Fixed Part (CC)

The component of space complexity that accounts for memory required by instruction space (byte code), simple variables, fixed-size variables, and constants, independent of input size.

7
New cards

Variable Part (S(instance)S(\text{instance}))

The component of space complexity that depends on the problem input size nn, covering memory dynamically allocated for dynamic variables, function call stacks, and recursive calls.

8
New cards

Big-Oh Notation (OO)

An asymptotic notation stating that f(n)f(n) is O(g(n))O(g(n)) if the growth rate of f(n)f(n) is asymptotically less than or equal to g(n)g(n), providing an upper bound on running time or space.

9
New cards

Big-Omega Notation (Ω\Omega)

An asymptotic notation stating that f(n)f(n) is Ω(g(n))\Omega(g(n)) if f(n)f(n) is asymptotically greater than or equal to g(n)g(n), providing an asymptotic lower bound.

10
New cards

Big-Theta Notation (Θ\Theta)

An asymptotic notation stating that f(n)f(n) is Θ(g(n))\Theta(g(n)) if f(n)f(n) is asymptotically equal to g(n)g(n), providing an asymptotically tight bound.

11
New cards

Divide-and-Conquer Paradigm

An algorithm design paradigm that divides input data SS into two or more disjoint subsets, conqu