Explain what Big O notation is and why web developers should know about it:
Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.
Explain what a quadratic function (O(n2)) is:
The complexity of an algorithm is said to be quadratic when the steps required to execute an algorithm are a quadratic function of the number of items in the input. Quadratic complexity is denoted as O(n^2).
Example of JavaScript code that is O(n2):
void printAllPossibleOrderedPairs(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
printf("%d = %d\n", arr[i], arr[j]);
}
}
}
Here we're nesting two loops. If our array has n items, our outer loop runs n times and our inner loop runs n times for each iteration of the outer loop, giving us n2 total prints. Thus this function runs in O(n2) time (or "quadratic time"). If the array has 10 items, we have to print 100 times. If it has 1000 items, we have to print 1000000 times.
Linear search
looks down a list, one item at a time, without jumping. In complexity terms this is an O(n) search - the time taken to search the list gets bigger at the same rate as the list does.
Binary search
is when you start with the middle of a sorted list, and see whether that's greater than or less than the value you're looking for, which determines whether the value is in the first or second half of the list. Jump to the half way through the sublist, and compare again etc. This is pretty much how humans typically look up a word in a dictionary (although we use better heuristics, obviously - if you're looking for "cat" you don't start off at "M"). In complexity terms this is an O(log n) search - the number of search operations grows more slowly than the list does, because you're halving the "search space" with each operation.
Compare a linear search with a binary search algorithm:
Binary search requires the input data to be sorted; linear search doesn't
Binary search requires an ordering comparison; linear search only requires equality comparisons
Binary search has complexity O(log n); linear search has complexity O(n) as discussed earlier
Linear search algorithm code:
function linearSearch(arr, key){
for(let i = 0; i < arr.length; i++){
if(arr[i] === key){
return i
}
}
return -1
}
Binary search algorithm code:
function binarySearch(sortedArray, key){
let start = 0;
let end = sortedArray.length - 1;
while (start <= end) {
let middle = Math.floor((start + end) / 2);
if (sortedArray[middle] === key) {
// found the key
return middle;
} else if (sortedArray[middle] < key) {
// continue searching to the right
start = middle + 1;
} else {
// search searching to the left
end = middle - 1;
}
}
return -1;
}
Describe what the Fibonacci sequence is:
Fibonacci Sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... The next number is found by adding up the two numbers before it: the 2 is found by adding the two numbers before it (1+1), the 3 is found by adding the two numbers before it (1+2), the 5 is (2+3), and so on!
Fibonacci sequence using recursion:
function fibonacci(num) {
if (num < 2) {
return num;
} else {
return fibonacci(num - 1) + fibonacci(num - 2);
}
}
if (5 <= 0) {
console.log("Enter a positive integer.");
} else {
for (let i = 0; i < 6; i++) {
console.log(fibonacci(i));
}
}
Code that write the first 5 numbers in the Fibonacci sequence using Loop:
let n1 = 0;
let n2 = 1;
next;
for (let i = 1; i <= 5; i++) {
console.log(n1);
nextTerm = n1 + n2;
n1 = n2;
n2 = next;
}
Which algorithm is the more efficient solution to the problem:
A recursive function in general has an extremely high time complexity while a non-recursive one does not.
A recursive function generally has smaller code size whereas a non-recursive one is larger.
Reference:
Top comments (0)