Algorithms

Question 1

What is linear search?

Answer 1

In linear search, the idea of the algorithm is to iterate across the array from left to right, searching for a specified element.

In pseudocode:
*Repeat, starting at the first element:
* If the first element is what you’re looking for (the target), stop.
*Otherwise, move to the next element.

Question 2

What is big O notation

Answer 2

Big O Notation is a tool used to describe the time complexity of algorithms. It calculates the time taken to run an algorithm as the input grows. In other words, it calculates the worst-case time complexity of an algorithm. Big O Notation in Data Structure describes the upper bound of an algorithm’s runtime

It helps programmers calculate the scalability of an algorithm or count how many steps it must execute to give output based on data the program works on

Question 3

What is the runtime complexity of linear search?

Answer 3

Runtime Complexity for Linear Search = O(n)
It’s, as the name says, linear
one extra ‘item’ adds one extra ‘unit of time’

Question 4

What is binary search?

Answer 4

the idea of the algorithm is to divide and conquer, reducing the search area by half each time, trying to find a target number.

Question 5

What is needed to do binary search?

Answer 5

In order to leverage the power of binary search, our array must first be sorted, else we cannot make assumptions about the array’s contents.

Question 6

What is the pseudocode of Binary search

Answer 6

Repeat until the (sub)array is of size 0:
*Calculate the middle point of the current (sub)array.
*If the target is at the middle, stop.
*Otherwise, if the target is less than what’s at the middle, repeat,
changing the end point to be just to the left of the middle.
*Otherwise, if the target is greater than what’s at the middle, repeat, changing the start point to be just to the right of the middle.

Question 7

What is the runtime complexity of binary search?

Answer 7

Runtime Complexity for binary = O(log n)

this means: for every item added the number of operations grows very slowly.

log(n) is 2^N = value (N = the power is needed to reach that value

Question 8

Name 3 ways to sort an array

Answer 8

Selection sort, Bubble sort, Merge sort

Question 9

What is Bubble sort?

Answer 9

In bubble sort, the idea of the algorithm is to move higher valued elements generally towards the right and lower value elements generally towards the left.

Question 9

What is de pseudocode of Bubble Sort

Answer 9

*Set swap counter to a non-zero value
*Repeat until the swap counter is 0:
* Reset swap counter to 0
* Look at each adjacent pair
* If two adjacent elements are not in order, swap them and
add one to the swap counter

Question 10

Worst case scenario when using bubble sort?

Answer 10

The array is in reverse order; we have to “bubble” each of the n-elements all the way across the array, and since we can only fully bubble one element into position per pass, we must do this n times.

Question 11

Best case scenario when using bubble sort?

Answer 11

The array is already perfectly sorted, and we make no swaps on the first pass.

Question 12

What is the runtime complexity of bubble sort?

Answer 12

Runtime Complexity for bubble sort = O(N²)

Best case is O(n) = when array is already sorted

Question 13

What is selection sort?

Answer 13

In selection sort, the idea of the algorithm is to find the smallest unsorted element and add it to the end of the sorted list.

Question 14

What is de Pseudocode of selection sort

Answer 14

*Repeat until no unsorted elements remain:
*Search the unsorted part of the data to find the smallest value
*Swap the smallest found value with the first element of the unsorted part

Question 15

What is the runtime complexity of selection sort?

Answer 15

Runtime Complexity for selection sort = O(N²)

Runtime for best- and worse case are exactly same because you need to check every item for each item

Question 16

What is merge sort?

Answer 16

In merge sort, the idea of the algorithm is to sort smaller arrays and then combine those arrays together (merge them) in sorted order.

Question 17

What is merge sort in Pseudocode?

Answer 17

*Sort the left half of the array (assuming n> 1)
*Sort the right half of the array (assuming n> 1)
*Merge the two halves together

Question 18

What is the runtime complexity of merge sort?

Answer 18

Runtime Complexity for selection sort =O(n log n)

Worst-case scenario: We have to split n elements up and then recombine them, effectively doubling the sorted subarrays as we build them up. (combining sorted 1-element arrays into 2-element arrays, combining sorted 2-element arrays into 4-element arrays…)

Question 19

What is recursion?

Answer 19

*We might describe an implementation of an algorithm as being particularly “elegant” if it solves a problem in a way that is both interesting and easy to visualize.

*The technique of recursionis a very common way to implement such an “elegant” solution.

*The definition of a recursive function is one that, as part of its execution, invokes itself.