C949 WGU - Algorithms

C949 WGU - Algorithms Leave the first rating Students also studied Terms in this set (35) Science Computer Science Algorithms Save 2.5 - Representing Instructions to th...32 terms anthonymartinez10 Preview Logistic Regression Teacher 37 terms melissa_mcmahan Preview Homework #8 16 terms Bear0026Preview Data St

• terms

t_ca Practice questions for this set Learn1 / 7Study using Learn look for "swap"/"exchange" in code so the result floats or 'bubbles' to the top.O(N^2).Deleting from the front of an array is ....O(N) since we have to shift all the data over to fill the gap created at index 0 (the front of the array) Choose an answer 1Deleting from the front of an array is .... 2

Radix:

Big O - Fast or not?

3Bubble reminders:4Reading from a linked list worst-case is....

Don't know?

Deleting from the end of an array is....O(1); as in deleting from a priority queue (where the end of the array is actually the front of the priority queue) Insertion into an ordered array is ....O(N) since we have to inspect up to all N elements of the array to determine where our new data should go.Reading from an array is .....O(1) Reading from a linked list worst-case is....O(N) Linear search time, because the computer would have to read every value in turn Selection Sort Big O - Fast or not?Best - Ω(n^2) Average - Θ(n^2) Worst - O(n^2) Not Fast

Insertion:

Big O - Fast or not?Best- Ω(n) Average - O(N^2) Worst - O(N^2) not fast

Bubble:

Big O - Fast or not?Best - Ω(n) Average - O(N^2) Worst - O(N^2) speed dependent on size (small is better and faster)

Shell:

Big O - Fast or not?Best - Ω(n log(n)) Average - Θ(N^1.5) Worst - O(n(log(n))^2) not fast

Quicksort:

Big O - Fast or not?Best - Ω(n log(n)) Average - O(n log(n)) Worst - O(n^2) yes fast

Merge:

Big O - Fast or not?Best - Ω(n log(n)) Average - O(n log(n)) Worst - O(n log(n)) yes fast Bucket SortBest - Ω(n+k) Average - Θ(n+k) Worst - O(n^2) yes fast

Radix:

Big O - Fast or not?Best - Ω(nk) Average - O(nk) Worst - O(nk) yes fast

Heap :

Big O - Fast or not?Best - Ω(N) Average - O(n log(n)) Worst - O(n log(n)) yes fast If the number of steps stays the same no matter how large N gets...then it has constant time complexity O(1) If steps go through N-long list in a linear fashion (if you see an iteration loop i++ situation ) then it will take at most N steps, O(N) If you go through an N long list AND do N things each time (if you find a loop inside a loop for example) then it is O(N^2) . "nesting iterations" = exponentials. two nested loops? O(N^3).three? O(N^4). and so on.

If you combine O(1) and O(N^2) , as in: the number of

steps stays the same but also includes a linear for loop, then O(N + N^2), but we just say O(N^2), as the notation is simplified.Bubble reminders:look for "swap"/"exchange" in code so the result floats or 'bubbles' to the top.O(N^2).Bucket reminders:look for code distributing values into buckets where they are individually sorted.Best used for input that is evenly distributed over a range.Binary hints:: O(logN) because growth curve produces by continually halving has little effect on growth after a few iterations Merge hints:: look for something that continually splits a list in half Quicksort hints:look for keywords: "pivot"

Radix hints:sorting by least/most significant digits

O(1)Constant O(log(n))Logarithmic O(log^c(n))Polylogarithmic O(n)Linear O(n log(n))Linearithmic / Loglinear O(n2)Quadratic

O(n3)Polynomial O(2n)Exponential O(n!)Factorial Sequential Searchtraverse through all the elements sequentially and check all the elements.Interval SearchThe array is divided into 2 or 3 intervals at every stage. After dividing the array into intervals, we determine the interval at which the element to be found is expected and further divide that interval into 2 or 3 sub-intervals and follow the same process until the length of the sub-interval becomes 0.