Software Engineering Flashcards
(36 cards)
Big o notation for 000.5n^3
n^3 we ignore all smaller terms, do some big O exampels
BIG 0 order
2^N>n^3>N^2logn>N^2>NlogN>n>1(constant)
Big O, O(x+Y)
the greater of x or y
Big) (XY)
OxOy
Bubble sort
start at index o
compare with item next to you. if its less than you, swap,
incriment.
repeat whole list until there are no swaps
total passes for bubble sort of n length
n(n-1)/2
bubble sort time
best O(n)
avg n^2
worst n^2
Insertion sort
assume first item is sorted.
place the next item in the correct spot for the sorted section.
increase the sorted seciton
total passes for insertion sort
n-1
insertion sort time
best n
worst n^2
avg n^2
selection sort
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
seleciton sort time
n^2 all
merge sort
Find the middle point to divide the array into two halves:
middle m = (l+r)/2
2. Call mergeSort for first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)
merge sort timing
nlogn for all
Pivot sort
Pick a “pivot”
- Divide into less-than & greater-than pivot
- Sort each side recursively
Binary search
Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you’ve narrowed down the possible locations to just one
benefits of linked lists
no needed size, dynamic, timing is all On but o1 for insert at end
GO OVER CREATION AND ALGORITHM STUFF
adding data to stack
Go over stack stuff
push and pop affect stuff on top only
enqueue
getting into the queue
dequeue
gettingout of the querye, have been served
peek
The peek() method of Queue Interface returns the element at the front the container. It does not deletes the element in the container.
queue follows
FIFO
in order tree traversal
visit left subtree, then root then right
pre order tree traversal
visit current node, then left, then right
