The Last Algorithm Course Flashcards
What is the simplest Data Structure?
An array
What is Big O?
It is a way to categorize an algorithms time or memory requirements based on input
Why do we use Big O?
It will help us make decisions about what data structures and Algorithms to use. Knowing how they perform can help us make the best possible program.
What is the running time of this algorithm?
function sum_char_codes (n: string): number {
let sum = 0;
for (let i = 0; i < n.length; ++i) {
sum += n. charCodeAt (i) ;
}
return sum;
}
O(N)
What are the 3 concepts for time and space complexity?
1.Growth with respect to input
2.Constants are always dropped
3.Worst case is usually the way we measure
What is the running time of this algorithm?
function sum_ char_ codes (n: string) : number {
let sum = 0;
for (let i = 0; i < n.length; ++i) {
sum += n. charCodeAt (i) ;
}
for (let i = 0; i < n.length; ++i) {
sum += n. charCodeAt (i) ;
}
return sum;
}
O(N)
What is the running time of this algorithm?
function sum_ char_ codes (n: string) : number {
let sum = 0;
for (let i = 0; i < n.length; ++i) {
const charCode = n. charCodeAt (i) ;
// Capital E
if (charCode === 69) {
return sum;
}
sum += charCode;
}
return sum;
}
O(N)
(O of N)
What is the running time of this algorithm?
function sum char codes (n: string): number {
let sum = 0;
for (let i = 0; i < n. length; ++i) {
for (let j = 0; j < n.length; ++j) {
sum += charCode;
}
}
return sum;
}
O(N^2)
What is the running time of this algorithm?
function sum char_codes (n: string): number {
let sum = 0;
for (let i = 0; i < n. length; ++i) {
for (let j = 0; j < n.length; ++j) {
for (let k = 0; k < n. length; ++k) {
sum += charCode;
}
}
}
return sum;
}
O(N^3)
An example of O(n log n)
Quicksort
An example of O(log n)
Binary search trees
This is an example of what?
export default function bs_list(haystack: number[], needle: number): boolean
{
6 }
let 10 = 0;
let hi = haystack. length;
do {
const m = Math. floor(lo + (hi - 10) / 2);
const v = haystack[m];
if (v === needle) {
return true;
7 else if (v > needle) §
hi = m;
† else {
10 = m + 1;
구
} while (lo < hi);
return false;
Binary Search
What is the running time of Bubble Sort?
O(n^2)
What sucks about an array?
Deletion ( you can’t delete but can zero out something)
Insertion (you can’t insert, but you can write)
It’s Ungrowable
What is the running time from deleting or inserting in a linked list?
O(1)
What kind of structure is a queue?
FIFO (First In First Out)
What is the opposite of a Queue?
A Stack
For a linked list, what’s the only way you’re able to search for an item?
Using linear search
TRUE or FALSE:
There is no such thing as a binary search on a linked list
True
Which one is better? An array list or linked list?
It depends on the situation. If you are popping or pushing from the end, then any can work well.
There’s a trade off
Getting sucks on linked list. Removing from the front sucks on array list because then you have to move all the other values to the left by one.
