Dev Tech Question: What Are These Things?

Every Thursday, I post a question for The Dev Tech Question. This article is for the post on Thu March 18, 2021.

Questions:

The three questions asked were:

1. What is a DOM?
2. What is a CORS
3. What is Big-O-Notation?

Answers:

A great summarized answer commented by one of the community members, Kimatia J Dan:

DOM is the document object model used to manipulate the events without necessarily refreshing the browser.
CORS is cross-origin resource sharing which is a security mechanism that allows trusted requests from trusted apps to communicate with backend services.
Big o notation is a measure of how an algorithm will perform in worst-case scenarios.

What is the DOM?

Answer

The DOM (Document Object Model) is a cross-platform API that treats HTML and XML documents as a tree structure consisting of nodes. These nodes (such as elements and text nodes) are objects that can be programmatically manipulated and any visible changes made to them are reflected live in the document. In a browser, this API is available to JavaScript where DOM nodes can be manipulated to change their styles, contents, placement in the document, or interacted with through event listeners.

What is CORS?

Answer

Cross-Origin Resource Sharing or CORS is a mechanism that uses additional HTTP headers to grant a browser permission to access resources from a server at an origin different from the website origin.

An example of a cross-origin request is a web application served from http://mydomain.com that uses AJAX to make a request for http://yourdomain.com.

For security reasons, browsers restrict cross-origin HTTP requests initiated by JavaScript. XMLHttpRequest and fetch follow the same-origin policy, meaning a web application using those APIs can only request HTTP resources from the same origin the application was accessed, unless the response from the other origin includes the correct CORS headers.

What is Big O Notation?

Answer

Big O notation is used in Computer Science to describe the time complexity of an algorithm. The best algorithms will execute the fastest and have the simplest complexity.

Algorithms don't always perform the same and may vary based on the data they are supplied. While in some cases they will execute quickly, in other cases they will execute slowly, even with the same number of elements to deal with.

In these examples, the base time is 1 element = 1ms.

O(1)

arr[arr.length - 1]

• 1000 elements = 1ms

Constant time complexity. No matter how many elements the array has, it will theoretically take (excluding real-world variation) the same amount of time to execute.

O(N)

arr.filter(fn)

• 1000 elements = 1000ms

Linear time complexity. The execution time will increase linearly with the number of elements the array has. If the array has 1000 elements and the function takes 1ms to execute, 7000 elements will take 7ms to execute. This is because the function must iterate through all elements of the array before returning a result.

O([1, N])

arr.some(fn)

• 1000 elements = 1ms <= x <= 1000ms

The execution time varies depending on the data supplied to the function, it may return very early or very late. The best case here is O(1) and the worst case is O(N).

O(NlogN)

arr.sort(fn)

• 1000 elements ~= 10000ms

Browsers usually implement the quicksort algorithm for the sort() method and the average time complexity of quicksort is O(NlgN). This is very efficient for large collections.

O(N^2)

for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length; j++) {
    // ...
  }
}

• 1000 elements = 1000000ms

The execution time rises quadratically with the number of elements. Usually the result of nesting loops.

O(N!)

const permutations = arr => {
  if (arr.length <= 2) return arr.length === 2 ? [arr, [arr[1], arr[0]]] : arr
  return arr.reduce(
    (acc, item, i) =>
      acc.concat(
        permutations([...arr.slice(0, i), ...arr.slice(i + 1)]).map(val => [
          item,
          ...val
        ])
      ),
    []
  )
}

• 1000 elements = Infinity (practically) ms

The execution time rises extremely fast with even just 1 addition to the array.