Basic Algorithms
Binary Search:
Binary Search is an algorithm based on sorted array. The flow of this algorithm is that: you repeatedly dividing in half the portion of the array. And check if the middle element of the initial array is bigger or smaller then your target element. if bigger, do the same to the right (higher) part of the array, if smaller take the left (lower) part of the array. Repeat this operation till you can not continue to split the array in half. here is a visual explanation:
Why does this algorithm exist?
A very efficient way of finding an element in sorted array (in the same type).
Pros: one of the most efficient way to find a element in sorted array. Cons: this algorithm works only on sorted arrays. In projects can be used in searching data throw some organized data base, such as a server with a lot of data. This algorithm optimized for searching in a given sorted arrays.
Time Complexity: Every time I double the number of element in the array I need to cut one more time the array(add an iteration). Thus O(log n).
TIP: when stuck in trying to find the time complexity of an algorithm, the best way is just creating a table of n verses iteration of the algorithm like this:
Recursion:
recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem
In the sort version is a function that calls itself, Here is an Example:
Why this method exists
Recursion is more readable for programmers. When using this method always best to think of the complexity, because it’s complexity tend to be high.
Algorithm Structure:
Recursion function have a structure that imported to follow. First, the function need to have a Base Case this condition needs to stop the infinite loop created by the function calling itself. Moreover, if the above conditions are False then call the Recursive function with smaller parameter. Every iteration we minimize our problem. The most imported thing with recursive function is to have Faith.
Pros: recursive function are more elegant then most functions. Cons: at most cases recursive function will be ineffective at their complexity.
Use:
In my projects I can use recursive functions for “check valid input” functions. Moreover, in some cases it’s more “easy” to use recursion. Examples for this are, binary trees, and quick sort algorithm, etc…
Time Complexity
The big O of recursive functions splits to sections according to the number of calls the function does in itself. when calling it self one time the complexity is linear. When the function call itself T times the complexity is O(T^n). And if we reduce the number of iteration by dividing in K the complexity is O(log(n)) — when the log is base K. For Visual examples click here.
Sorting Algorithms:
Sorting algorithms are very important especially when working with big data. The target in sorting is to get an array of elements arrange in specific order. For example array of integers can be sorted by value from smaller to highest, and vice versa.
Bubble Sort:
How does it work: given an array on N elements the algorithm go throw the elements and check if they need to switch. that way each round the largest element gets to the end of the array.
Pros: this sort is very easy to understand and implement. Cons: not very efficient.
Big O: O(n²), because for each element we need to do n -1 comparisons. Moreover, bubbles sort is a in-place sorting algorithm, because we didn’t use any more space then the given array.
Merge Sort:
How does it work: this sorting algorithm is based on Divide and Conquer algorithms. Means it’s dividing as much as possible and over time build it back up doing comparisons.
Pros: it’s time complexity is very low compare to other sorting algorithms. Cons: it’s space complexity isn’t in-place because we are splitting the array into little pieces.
Big O: time complexity is O(n log(n)), because every time we input array two times bigger the algorithm only use one more split. The space complexity is O(n), because every iteration we copied the array’s values to new array in the sum of n, and deleting the previous arrays.
Quick Sort:
How does it work: You pick a random element(Pivot element), move all values larger than it above it and all values below it lower than it. then you do the same to the upper and lower sections of the array.
Pros: at the average and best case quick sort have the same complexity of merge sort, O(n log(n)), but without the space complexity(in-place sort). Cons: at the worst case the complexity is like bubble sort O(n²)
Use in projects:
In most languages a sort function can be found in the language libraries, so there is no need to implement sorting algorithm. in many cases sorting can be helpful when using large amount of data, and presenting it to the user.
