Algorithms and Complexity
0.0(0)
Studied by 0 people
Call with Kai
Knowt Play
Learn
Practice Test
Spaced Repetition
Match
FlashcardsCard Sorting
1/14
There's no tags or description
Looks like no tags are added yet.
Study Analytics
Name | Mastery | Learn | Test | Matching | Spaced |
|---|
No study sessions yet.
15 Terms
1
New cards
problem
defined by input and correct output
2
New cards
algorithm
stepwise procedure, terminates, produces correct output
3
New cards
correctness
efficiency
key issues:
1.
2.
4
New cards
Big O
f(n) <= cg(n) for all n >= n0
(O(g(n))
5
New cards
Big Omega
lower bounded (>=)
(Ω(g(n))
6
New cards
Big Theta
bounded above and below (=)
(θ(g(n))
7
New cards
Little o
strictly upper bounded (<)
o(g(n))
8
New cards
Little omega
strictly lower bounded (>)
(ω(g(n))
9
New cards
query
search, retrieval, range
10
New cards
updates
insert, delete, change
11
New cards
space
measured in words/bits
12
New cards
O(1)
a single operation is ____ time
ex: arr[i] = 5;
13
New cards
O(n)
a loop that runs n times is ____ time
14
New cards
O(n²)
a nested loop is ____ time
15
New cards
O(log n)
dividing by n each time is ____ time
Note 
Flashcards (22)