var Component=(()=>{var g=Object.create;var r=Object.defineProperty;var d=Object.getOwnPropertyDescriptor;var A=Object.getOwnPropertyNames;var u=Object.getPrototypeOf,m=Object.prototype.hasOwnProperty;var p=(t,e)=>()=>(e||t((e={exports:{}}).exports,e),e.exports),w=(t,e)=>{for(var i in e)r(t,i,{get:e[i],enumerable:!0})},l=(t,e,i,a)=>{if(e&&typeof e=="object"||typeof e=="function")for(let o of A(e))!m.call(t,o)&&o!==i&&r(t,o,{get:()=>e[o],enumerable:!(a=d(e,o))||a.enumerable});return t};var f=(t,e,i)=>(i=t!=null?g(u(t)):{},l(e||!t||!t.__esModule?r(i,"default",{value:t,enumerable:!0}):i,t)),b=t=>l(r({},"__esModule",{value:!0}),t);var h=p((C,s)=>{s.exports=_jsx_runtime});var x={};w(x,{default:()=>B,frontmatter:()=>I});var n=f(h()),I={locale:"en",title:"Big O Notation",keywords:["algorithm","big-o","big-O(1)","big-O(n)","big-O(n^2)","big-O(log n)","big-O(n log n)","big-O(2^n)","big-O(n!)"],slug:"big-o-notation",createdAt:new Date(1679184e6),categorySlug:"algorithm",description:"Describing the time complexity of an algorithm",thumbnailLarge:"/images/big-o/geometry_1920x1077.jpg"};function c(t){let e=Object.assign({h2:"h2",p:"p",strong:"strong",code:"code",h4:"h4",pre:"pre",a:"a",h5:"h5",h3:"h3",blockquote:"blockquote",ul:"ul",li:"li",img:"img"},t.components);return(0,n.jsxs)(n.Fragment,{children:[(0,n.jsx)(e.h2,{children:"Introduction"}),` `,(0,n.jsx)(e.p,{children:`In our day-to-day as a developer, we constantly need to create scalable and high-performance algorithms. Defining a good implementation for our context will not always be an easy task.`}),` `,(0,n.jsx)(e.p,{children:`Many times, a runtime test may have been the only way used to measure your implementation. By the end of this post, I hope who can use Big O notation to understand the time complexity of their algorithm. And consequently become a better developer.`}),` `,(0,n.jsx)(e.h2,{children:"What is it ?"}),` `,(0,n.jsxs)(e.p,{children:[`Big O Notation is a mathematical notation for describing the time complexity of an algorithm in relation to performance changes in input size. It is used to describe the `,(0,n.jsx)(e.strong,{children:"worst case execution"})," of an algorithm. We can interpret the ",(0,n.jsx)(e.code,{children:"O"})," being the indicative for ",(0,n.jsx)(e.strong,{children:"processing time/cost"})," and ",(0,n.jsx)(e.code,{children:"n"}),` being the input elements.`]}),` `,(0,n.jsx)(e.h2,{children:"About the notations"}),` `,(0,n.jsx)(e.p,{children:`There are many Big O time complexity notations, but in this post we will see a little bit about O(1), O(n), O(n^2), O(log n), O(n log n), O(2 ^n) and O(n!).`}),` `,(0,n.jsxs)(e.h4,{children:[(0,n.jsx)(e.strong,{children:"O(1)"})," - constant time"]}),` `,(0,n.jsx)(e.p,{children:"In this notation, the running time of the algorithm does not vary with the input size. Keeping it that way, always constant."}),` `,(0,n.jsx)(e.p,{children:"For example:"}),` `,(0,n.jsx)(e.pre,{children:(0,n.jsx)(e.code,{className:"language-ts",children:`const getFirstElement = (list: Array) => list[0]; const smallList = Array.from({ length: 10 }, (_, i) => i + 1); console.log(getFirstElement(smallList)); // Output: 1 const mediumList = Array.from({ length: 10_000 }, (_, i) => i + 1); console.log(getFirstElement(mediumList)); // Output: 1 const largeList = Array.from({ length: 1_000_000 }, (_, i) => i + 1); console.log(getFirstElement(largeList)); // Output: 1 `})}),` `,(0,n.jsx)(e.p,{children:(0,n.jsx)(e.a,{href:"https://www.typescriptlang.org/play?#code/MYewdgzgLgBA5gUygMQJYCdoFEA2CC2CYsAvDADwAqANAHwAUOq0AXDAILroCGAnlbQCUMErRhNoAbQAMAXQDcAWABQK0JFgR83HDgAyzUhy58AdADN0IfPQDe4onCgALNgEZpMAL7UY9APq+qMKiMKgwANQwboJKyuoQIHimOCBw9IgoGNh4hMT0Wjr6hoKxMAD05TAA8gCuUAAO9e4qauDQMIQAJqi1+AYdZJw8vBZWNvZ4YE6u0dL+0ovevgFBIWLhUTFxCUkIKWkZSGiYULgERFD03b39JWWVNfVNUC2q8e2wONzoiANGwzMlmsdgc0xc7gWiyhnh8fkCYXWYUi0VibUgewO6UyJxyF3y31+CH+pXkFSqdUazWiQA",children:"Click here to open the playground"})}),` `,(0,n.jsx)(e.h5,{children:"Explanation of the algorithm"}),` `,(0,n.jsx)(e.p,{children:`In this example, we have a function that, when receiving a list, returns its first item. Regardless of the size of the list, we are always picking the same position. For this reason, we classify this algorithm as O(1).`}),` `,(0,n.jsx)(e.h4,{children:"O(n) - Linear time"}),` `,(0,n.jsx)(e.p,{children:"In this notation, the running time of the algorithm grows linearly with the size of the input."}),` `,(0,n.jsx)(e.p,{children:"For example:"}),` `,(0,n.jsx)(e.pre,{children:(0,n.jsx)(e.code,{className:"language-tsx",children:`var countIterations = 0; const searchItem = (list: Array, itemSearch: T): number => { const size = list.length; for (let i = 0; i < size; i++) { countIterations++; const currentItem = list[i]; if (currentItem === itemSearch) { return i; } } return -1; }; const numbers = Array.from({ length: 50 }, (_, i) => i); const indice = searchItem(numbers, 25); // Return: 25 console.log(numbers[indice]); // Output: 25 console.log(countIterations); // Output: 26 `})}),` `,(0,n.jsx)(e.p,{children:(0,n.jsx)(e.a,{href:"https://www.typescriptlang.org/play?#code/G4QwTgBAxg9grgOwC4EkkFMwiQSxggZwgF4IAGAbgFgAoW2QpCA9cKACzXQFsSIAeACoAaAHwAKADY4CSAFwQAgmCwBPIaOEQcGbgGVWYDgsEBKBQjjcARphKiIAb1oRo+WcxwAvdH2myAOkl0BABzJHZqGlcAMxhIKXQmHD5KbQFPHwptAGoc0ycXVzdEVAwsXHc8qOK3Rmg4FRCynj8ZJABtHABdKKLXHBiIcShGsGauXmJp7V0DNnYC52jaiHGkRoRtGuKAXyL9uhX1zYgAWgBGKN2+o4YPSxtMIlJlNQCYsBhucUcIYLCEQUAFYyBBdlpxAB9LQ4ArEBxw273ZIIAAmOCgvlILAWk3Ej1sYAIWgATMDTNkAPRUiAAJSSmwU5Po7hgwSCMFCBKsRIIXXRmPQ3UpEBpEAA8nAkAAHaXM4Gswjs9Cc7mwUpcCp4Qii8VS2XyiCkgBstFoQA",children:"Click here to open the playground"})}),` `,(0,n.jsx)(e.h5,{children:"Explanation of the algorithm"}),` `,(0,n.jsx)(e.p,{children:`In this example, we have a function that, when receiving a list, searches and returns the index of the searched element. In this search, the list will be traversed sequentially starting from the first item in the list. For this reason, to find the index of the number 25, 26 iterations are necessary (remember that the first iteration is for the index 0).`}),` `,(0,n.jsxs)(e.p,{children:[`If we now have a list with 1000 items, and we search for the 25 again, we still have 26 iterations, because the iteration is sequential. But, if we need to search for the number 1000, we will have 1001 iterations. Therefore, `,(0,n.jsx)(e.strong,{children:`the longer your list, the greater the number of iterations needed to find the worst case scenario`}),", which in this algorithm would be the last item in the list. For this reason, we classify it as O(n)."]}),` `,(0,n.jsx)(e.h3,{children:"O(n^2) - Quadratic time"}),` `,(0,n.jsx)(e.p,{children:"The running time of the algorithm grows in order of the square of the input size."}),` `,(0,n.jsx)(e.p,{children:"For example:"}),` `,(0,n.jsx)(e.pre,{children:(0,n.jsx)(e.code,{className:"language-tsx",children:`let countIterations = 0; const bubbleSort = (list: Array) => { const size = list.length; let isSwapped = false; for (let i = 0; i < size; i++) { isSwapped = false; for (let j = 0; j < size; j++) { countIterations++; if (list[j] > list[j + 1]) { var temp = list[j]; list[j] = list[j + 1]; list[j + 1] = temp; isSwapped = true; } } if (!isSwapped) { break; } } return list; }; console.log(bubbleSort([10, 9, 8, 7, 6, 5, 4, 3, 2, 1])); // Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] console.log({ countIterations }); // Output: 100 `})}),` `,(0,n.jsx)(e.p,{children:(0,n.jsx)(e.a,{href:"https://www.typescriptlang.org/play?#code/DYUwLgBAxg9grgOzASTCATgQzASxggZwgF4IAGAbgFgAoW2QyAIziadAGUZ1JSAeACoAaAHwAKYDgJgAXBACC6LAE9BIgJQkREAN60IB6PmkQCOAF4gSESdIB0oBAHMwAC2p0ahm+AhSOAO6YAA7BIAAm1gBmmMAEIB76hlHcEBK+ONaUfhB8phYJfgDURZp6Xt6G-kGhEdGx8YkVlRAp6GmgkABWWRQQPXlmln1dJWVJLd6wiChoWLjGJR6TlThRHVJgANpdALoQ2rbbPUUQAIy7480rlQBumO1oALbB1kc7uxM33u97b5s7CCnC7Lb6VX5A877UjPYKgsFVAiBEJhSIw9BwBJfFYAX2xhjxnhWazSAEJqiiIlcEUx0CBMABreGVQneQlfOlgODoBA2TYedk0BgEGCgBwwJxiFhsTjcMBiLZnMhCCAAThVAA4VQB2FUANhVAFYVQAWFUAZhVACYVRd1Oo+gB6R0QADycDAwQ9ckV1otpqN+p1mpV6vOZE+QuMopA4slOiMM1QGGweEIEBxDogzrdHq9snDZFoQA",children:"Click here to open the playground"})}),` `,(0,n.jsx)(e.h5,{children:"Explanation of the algorithm"}),` `,(0,n.jsx)(e.p,{children:`In this example, we have a function that, when receiving a list, sorts its values in ascending order. At each iteration we check the smallest number and place it in the first position, the second-smallest number in the second position, and so on.`}),` `,(0,n.jsxs)(e.p,{children:["As ",(0,n.jsx)(e.strong,{children:"we have nested loops"}),", our worst case is to receive a totally unordered list (like our example case). So result in iteration of ",(0,n.jsx)(e.code,{children:"n * n"}),`. For this reason, we classify it as O(n^2).`]}),` `,(0,n.jsx)(e.h4,{children:"O(log n) - Logarithm time"}),` `,(0,n.jsxs)(e.blockquote,{children:[` `,(0,n.jsxs)(e.p,{children:["\u26A0 Warning: If you don't understand about logarithm, I'll briefly explain.",(0,n.jsx)("br",{}),' If you already understand, feel free to skip the "What is logarithm"']}),` `]}),` `,(0,n.jsx)(e.h5,{children:"What is logarithm?"}),` `,(0,n.jsx)(e.p,{children:`Logarithms are the inverse of exponential. It is an operation that finds the exponent of a power when its base and result are known. Think about the following question:`}),` `,(0,n.jsxs)(e.p,{children:["What number do I use in exponentiation for 2 resulting in 16? That number would be 4. That is, ",(0,n.jsx)(e.code,{children:"4\xB2 = 16"}),`. That is, log in base 2 of 16 equals 4 `,(0,n.jsx)(e.code,{children:"log2(16) = 4"}),"."]}),` `,(0,n.jsxs)(e.p,{children:["Since logarithms are the inverse of exponentiation, we can find the number of operations using the logarithm of N. So ",(0,n.jsx)(e.code,{children:"log2(n) = x"}),", where ",(0,n.jsx)(e.code,{children:"x"}),` is the number of operations performed during the execution of the algorithm.`]}),` `,(0,n.jsx)(e.p,{children:"But it is worth remembering that the base will not always be 2."}),` `,(0,n.jsx)(e.h5,{children:"The annotation"}),` `,(0,n.jsx)(e.p,{children:"In this notation, the running time of the algorithm increases at a logarithmic rate with respect to the size of the input."}),` `,(0,n.jsx)(e.p,{children:"For example:"}),` `,(0,n.jsx)(e.pre,{children:(0,n.jsx)(e.code,{className:"language-tsx",children:`var countIterations = 0; const binarySearch = (list: Array, itemSearch: T): number => { let start = 0; let end = list.length; while (start <= end) { countIterations++; const mid = Math.floor((start + end) / 2); if (list[mid] === itemSearch) { return mid; } else if (list[mid] < itemSearch) { start = mid + 1; } else { end = mid - 1; } } return -1; }; const numbers = Array.from({ length: 50 }, (_, i) => i); const indice = binarySearch(numbers, 25); // Return: 25 console.log(numbers[indice]); // Output: 25 console.log(countIterations); // Output: 1 `})}),` `,(0,n.jsx)(e.p,{children:(0,n.jsx)(e.a,{href:"https://www.typescriptlang.org/play?#code/G4QwTgBAxg9grgOwC4EkkFMwiQSxggZwgF4IAGAbgFgAoW2QpCAIxwXAE8BldcKACxIQAPABUANAD4AFABscBJAC4IAQTBYOYyeIg4MAWx59+K0QEoVCOAeaYSkiAG9aECLPRNF4JqUqv3Twh0BAATIXlFADoPBABzJH5qOho3AHd+HA8IaW8wJmFSENDzZwC3WERUDCxcfAIAagbktwr6pgMccNIAWWx+KIAzWRgYMGlcpB8IBuCw0oB6CAAmc2TyvUGcyKQAbU7QgF0SYlJ9dCNeMAFSl1TWtzBPODAECAOW1oBfYNkCdE22wUewOx2EekMxmu-FuGzceV87y6MwgAEZPm4fug-gC7g83MUhAcIABaNEYiBfAJUlKPZ6vUno2hfdY0BiKCDWWyYIikdSaIZgGAGaROQLxRIqACsZEpumkAH1dDhSsRHCrWeymGxQjgoADSKx2GBuFcBNIuXYwARdMspWsIAslgAlekIFR2+j1GAeGIwOIWmxWgi7HV69CHB1OiAAeTgSAADvGPVKvYQfeg-QHKsg0JhsHhCFGlnHE8m0bRaEA",children:"Click here to open the playground"})}),` `,(0,n.jsx)(e.h5,{children:"Explanation of the algorithm"}),` `,(0,n.jsx)(e.p,{children:`In this example, we have a function that, upon receiving an ordered list and a value, searches and returns the index of the searched element. Unlike linear search which would scan item by item from beginning to end of the list. In this algorithm, we start from the middle of the list, and at each iteration we reduce the search size by half, until we reach 1.`}),` `,(0,n.jsx)(e.p,{children:`That is, in the first example where we searched for the number 25 in an ordered list with numbers from 0 to 50, it took only 1 iteration to find the index of 25. That is because 25 is half of 50, and our algorithm starts the search by the middle.`}),` `,(0,n.jsx)(e.p,{children:`If we now have a list with 1000 items, and we search for 25 again, we will have 10 iterations to find the index of 25. This is because the algorithm will reduce its search scope by half at each iteration.`}),` `,(0,n.jsxs)(e.p,{children:["Assuming you understood about logarithm, in this scenario our maximum number of possible operations would be ",(0,n.jsx)(e.strong,{children:"10"}),"."]}),` `,(0,n.jsxs)(e.blockquote,{children:[` `,(0,n.jsxs)(e.p,{children:["Calculation: ",(0,n.jsx)(e.code,{children:"log2(1000) = 9.965784284662087"})," (Just round it up and we get 10) ",(0,n.jsx)("br",{}),` If you don't believe me, I made a playground calculating the maximum number of possible operations. I looked for all the numbers from 0 to 999 and put a log in case any of them pass the maximum value. `,(0,n.jsx)("br",{}),` > `,(0,n.jsx)(e.a,{href:"https://www.typescriptlang.org/play?#code/G4QwTgBAxg9grgOwC4EkkFMwiQSxggZwgF4IAGAbgFgAoW2QpCAIxwXAE8BldcKACxIQAPABUANAD4AFABscBJAC4IAQTBYOYyeIg4MAWx59+K0QEoVCOAeaYSkiAG9aECLPRNF4JqUqv3Twh0BAATIXlFADoPBABzJH5qOho3AHd+HA8IaW8wJmFSENDzZwC3WERUDCxcfAIAagbktwr6pgMccNIAWWx+KIAzWRgYMGlcpB8IBuCw0oB6CAAmc2TyvUGcyKQAbU7QgF0SYlJ9dCNeMAFSl1TWtzBPODAECAOW1oBfYNkCdE22wUewOx2EekMxmu-FuGzceV87y6MwgAEZPm4fug-gC7g83MUhAcIABaNEYiBfAJUlKPZ6vUno2hfdY0BiKCDWWyYIikdSaIZgGAGaROQLxRIqVFkGWU3TSAD6uhwpWIjhVrPZHRAAA80JhsHhCEI+okolB0FlpKaBiM4stpFy7GACDEQgkYWtaPR6jAPDEYHFpAAiUT8AEGXU4Aw2Tk2Z0QGBbGAABwNdUISmDukjepqhvqXpSgzG2yCOCEZF0BBwAC8AaQnTy3RKknoRBAa-WKHomrD7pVkPrakbeeRPqx2GBuFcBI74zzlUWAjgttJB9V06OII5pf2Huy-egA0HQ5kiHaIGksrJOehgPY7BBQgoU7IQBx0KFg0XMczvTQQA",children:"Click here to open the playground"})]}),` `]}),` `,(0,n.jsx)(e.pre,{children:(0,n.jsx)(e.code,{className:"language-tsx",children:`const numbers = Array.from({ length: 1_000 }, (_, i) => i); const indice = binarySearch(numbers, 25); // Return: 25 console.log(numbers[indice]); // Output: 25 console.log(countIterations); // Output: 10 /** * Iteration 1: 1000 itens * Iteration 2: 500 itens * Iteration 3: 250 itens * Iteration 4: 125 itens * Iteration 5: 62 itens * Iteration 6: 31 itens * Iteration 7: 15 itens * Iteration 8: 7 itens * Iteration 9: 3 itens * Iteration 10: 1 item **/ `})}),` `,(0,n.jsxs)(e.p,{children:["That is, as we decrease the amount of ",(0,n.jsx)(e.code,{children:"n"})," at each iteration, this is why we classify it as O(log n)."]}),` `,(0,n.jsx)(e.h3,{children:"O(n log n) - Quasilinear time"}),` `,(0,n.jsx)(e.p,{children:"In this notation, the running time of the algorithm increases at a slightly faster than logarithmic rate with respect to the size of the input."}),` `,(0,n.jsx)(e.p,{children:"For example:"}),` `,(0,n.jsx)(e.pre,{children:(0,n.jsx)(e.code,{className:"language-tsx",children:`let countIterations = 0; const merge = (left: Array, right: Array): Array => { let list: Array = []; while (left.length && right.length) { countIterations++; if (left[0] < right[0]) { list.push(left.shift()!); } else { list.push(right.shift()!); } } return [...list, ...left, ...right]; }; const mergeSort = (list: Array): Array => { const half = list.length / 2; if (list.length < 2) { countIterations++; return list; } const left = list.splice(0, half); return merge(mergeSort(left), mergeSort(list)); }; const numbers = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]; const size = numbers.length; const maxIterations = Math.ceil(size * Math.log2(size)); console.log({ maxIterations }); // Output: 34 console.log(mergeSort(numbers)); // Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] console.log({ countIterations }); // Output: 29 `})}),` `,(0,n.jsx)(e.p,{children:(0,n.jsx)(e.a,{href:"https://www.typescriptlang.org/play?#code/DYUwLgBAxg9grgOzASTCATgQzASxggZwgF4IAGAbgFgAoW2QyAWwwHMQSIAeAFQBoAfAApQAMzAAuCAEF0WAJ68BfCOhysAFpJlzMingICUU2QqUkBEAN60IdiKEjAcBbab3nSAbQC6tW-YA7ho4oBAiIOIAdKAIrGAaEABkSarqWjEgcQmG1gH29rCIKGhYuPgEANSV1DQFBTii4WJgXmQ+3Gmare25NnX1g86uUQAOcAQaEdGTjWBChgCEhvn1AL4QIMAEHP2DQy5gYxNTat1Rs+ILy6sFa6v3dAN26OBw6AgQXlE-w2AqP0y4gBPzOWj8NEe9AqzDYIAAyjB0JBSLxBCJDiZdPojFizAYLHlntAYRANJhgE1SH9MtlEgB6CAAJn8xMazUOtPiiS4zL6t0K8CQqAw2DwhGqtX2qjeHwchwerIKDFcDkiKPlIwIo2cUBAQjIKnJlJWxNeYHenxY6HYQmt7ERyOmYEMKntCKR8z+hlNUJoKsgCDgTAARhgiN4AIyGiAAThUAA4VAB2FQANhUAFYVAAWFQAZhUTJUkZ8tWhjAgBBwAC8OKQg6Hw1yEuX-aSmJgAB4isriiMQACy2A0UT1oSE1brEAAVEORzEYKwmZPayAfW2VTBQIvWEIrBBOz3SmKKhA1oYKBB6YyAPJwMDjbQAP3zOdZW53wCXdrhjvmjZhugBAbted4Pk+UheJGRYFrmWbpimiYqPGEDRhCn4gLu+4ksUvanoQ56XmBED3o+D5SEysa0EAA",children:"Click here to open the playground"})}),` `,(0,n.jsx)(e.h5,{children:"Explanation of the algorithm"}),` `,(0,n.jsx)(e.p,{children:"In this example, we have a sorting algorithm, which uses the technique of divide and conquer."}),` `,(0,n.jsxs)(e.p,{children:["The ",(0,n.jsx)(e.code,{children:"merge"})," function takes two sorted lists and merges them into a single sorted list."]}),` `,(0,n.jsxs)(e.p,{children:["The ",(0,n.jsx)(e.code,{children:"mergeSort"})," function takes a list and returns a sorted list."]}),` `,(0,n.jsxs)(e.p,{children:["As in the ",(0,n.jsx)(e.code,{children:"merge"})," function we have a complexity of O(n) - since we go through each item in the list - and in the ",(0,n.jsx)(e.code,{children:"mergeSort"}),` function we have O(log n) - since we divide the list -. With the sum of the complexities, we arrive at O(n log n)`]}),` `,(0,n.jsxs)(e.blockquote,{children:[` `,(0,n.jsxs)(e.p,{children:["As we did in the section on O(log n), to calculate the maximum number of approximate operations for this algorithm, we just need to do: ",(0,n.jsx)("br",{}),` n = Total size of items in the example `,(0,n.jsx)("br",{})," n = 10 ",(0,n.jsx)("br",{})," 10 * log2(10) = ~34"]}),` `]}),` `,(0,n.jsxs)(e.blockquote,{children:[` `,(0,n.jsxs)(e.p,{children:["\u26A0 Warning: If you want to know more about the algorithm, access the link ",(0,n.jsx)(e.strong,{children:"Merge Sort In JavaScript"}),", in the references section of this post."]}),` `]}),` `,(0,n.jsx)(e.h3,{children:"O(2^n) - Exponential time"}),` `,(0,n.jsx)(e.p,{children:"In this notation, the running time of the algorithm increases exponentially with the size of the input."}),` `,(0,n.jsx)(e.p,{children:"For example:"}),` `,(0,n.jsx)(e.pre,{children:(0,n.jsx)(e.code,{className:"language-tsx",children:`const generateSubsets = (list: T[]): T[][] => { const result: T[][] = []; const backstrack = (current: T[], index: number) => { if (index === list.length) { result.push(current); return; } const nextIndex = index + 1; backstrack(current, nextIndex); backstrack(current.concat(list[index]), nextIndex); }; backstrack([], 0); return result; }; const numbers = [1, 2, 3]; const result = generateSubsets(numbers); console.log(result); // Output: [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]] `})}),` `,(0,n.jsx)(e.p,{children:(0,n.jsx)(e.a,{href:"https://www.typescriptlang.org/play?#code/MYewdgzgLgBA5gUzAgTgQyggygVwEYQJQQwC8MAPACoA0AfABQA2AltAFwxUDaAugJScevPmTowA3gFgAUDHkxQkWCgQQcTKEL6jyfANyzZCxeGgw8aYAGto6G2RgNgOFKrBaufGjBZgAJggAHpxgOAC2eKj8YpLGJgosAGZOfoFBZKTkrNAAdExIcFAAFjHScgmVquqauQAOOBDFzq7uUPyGFZUmqlCuYJ3dMAC+8ZVK5shBUACSAcGOaQsA1DAAjIPdljZ2VtYtbkhQPlOz80EdYwnbtlD2+y6HHrlKwBjMbFDcS0ECJ8FndL8K6jGRXG67GwMbwwAAMlzBXRgvX6yLUGigRhkoNkE1gYUiqBIejWPgATD4AMy8Tq4swqdGaRyIZDoTC4AhECAMAlRFAQBETEAFfIgOAMaoYjowAD0MpgAHkcFAGp4YNwYdxqT5uGTeDqKTBteq1vqTVSzdxSTA9TrrYbqbwYEA",children:"Click here to open the playground"})}),` `,(0,n.jsx)(e.h5,{children:"Explanation of the algorithm"}),` `,(0,n.jsxs)(e.p,{children:[`In this example, we have a function that generates all possible combinations from a list. For each element in our list, two recursive calls are made. That is, as our input has 3 items, we have a total of `,(0,n.jsx)(e.code,{children:"2\xB3 = 8"})," operations. A list with 15 items, for example, would result in 32,768 operations."]}),` `,(0,n.jsx)(e.h2,{children:"O(n!) - Factorial time"}),` `,(0,n.jsx)(e.p,{children:"In this notation, the running time of the algorithm increases factorially according to the input size."}),` `,(0,n.jsx)(e.p,{children:"For example:"}),` `,(0,n.jsx)(e.pre,{children:(0,n.jsx)(e.code,{className:"language-tsx",children:`const permute = (value: string) => { const result: string[] = []; const usedChars: string[] = []; const backtrack = (text: string, current: string) => { if (current.length === text.length) { result.push(current); return; } for (let i = 0; i < text.length; i++) { const item = text[i]; if (!usedChars.includes(item)) { usedChars.push(item); backtrack(text, current + item); usedChars.pop(); } } }; backtrack(value, ""); return result; }; const input = "abcdef"; const chars = permute(input); // ["abcdef", "abcdfe", "abcedf", "abcefd", "abcfde", "abcfed", "abdcef", "abdcfe", "abdecf", "abdefc" ...] console.log(chars.length); // 720 // 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720 `})}),` `,(0,n.jsx)(e.p,{children:(0,n.jsx)(e.a,{href:"https://www.typescriptlang.org/play?#code/MYewdgzgLgBA5gUzAgTgQyggygVwEYQJQQwC8MAPACoA0AfABQA2AltAFwxUDaAugJScevPmTowA3gFgAUDHkxQkWCgQQcTKEL6jyfANyzZCxeGgw8aYAGto6G2RgNgOFKrBaufGjBZgAJggAHpxgOAC2eKj8YpLGJgosAGZOfoFBZKTkrNAAdExIcFAAFjHScgmVquqauQAOOBDFzq7uUPyGFZUmqlCuYJ3dMAC+8ZVK5shBUACSAcGOaQsA1DAAjIPdljZ2VtYtbkhQPlOz80EdYwnbtlD2+y6HHrlKwBjMbFDcS0ECJ8FndL8K6jGRXG67GwMbwwAAMlzBXRgvX6yLUGigRhkoNkE1gYUiqBIejWPgATD4AMy8Tq4swqdGaRyIZDoTC4AhECAMAlRFAQBETEAFfIgOAMaoYjowAD0MpgAHkcFAGp4YNwYdxqT5uGTeDqKTBteq1vqTVSzdxSTA9TrrYbqbwYEA",children:"Click here to open the playground"})}),` `,(0,n.jsx)(e.h5,{children:"Explanation of the algorithm"}),` `,(0,n.jsxs)(e.p,{children:[`In this example, we have a function that generates all permutations of a text. In it, we have an iteration and recursion that for each time it is called, it sends as input one less character of the input text. We have 6 letters, that is, as we have the iteration O(n) and the recursion always passing n-1, we arrive at the notation O(n!). Resulting in `,(0,n.jsx)(e.code,{children:"n! = 6! = 6 * 5 * 4 * 3 * 1 = 720"})," operations."]}),` `,(0,n.jsx)(e.h2,{children:"Conclusion"}),` `,(0,n.jsx)(e.p,{children:`We've seen some examples and because we rank an algorithm in a certain notation. For each notation, it was possible to see how problematic it becomes according to the size of the input. Among those mentioned, there is a classification to help you know how good it is, being:`}),` `,(0,n.jsxs)(e.ul,{children:[` `,(0,n.jsx)(e.li,{children:"O(n!), O(2^n) e O(n^2) - Horrible"}),` `,(0,n.jsx)(e.li,{children:"O(n log n) - Bad"}),` `,(0,n.jsx)(e.li,{children:"O(n) - Fair"}),` `,(0,n.jsx)(e.li,{children:"O(log n) - Good"}),` `,(0,n.jsx)(e.li,{children:"O(1) - Excellent"}),` `]}),` `,(0,n.jsx)(e.p,{children:"See in the illustration:"}),` `,(0,n.jsx)(e.p,{children:(0,n.jsx)(e.img,{src:"/images/big-o/big-o-classification.png",alt:"Imagem indicando que O(n!), O(2^n) e O(n^2) s\xE3o nota\xE7\xF5es que classificam o algoritmo como horr\xEDvel. O(n log n) classifica como ruim. O(n) classifica como justo. O(log n) classificado como bom. E O(1) classificado como excelente",title:"Big O classifica\xE7\xE3o"})}),` `,(0,n.jsx)(e.h2,{children:"References"}),` `,(0,n.jsxs)(e.ul,{children:[` `,(0,n.jsx)(e.li,{children:(0,n.jsx)(e.a,{href:"https://www.alura.com.br/artigos/como-classificar-algoritmos-big-o-notation",children:"Como classificar algoritmos com Big O Notation"})}),` `,(0,n.jsx)(e.li,{children:(0,n.jsx)(e.a,{href:"https://medium.com/linkapi-solutions/o-que-%C3%A9-big-o-notation-32f171e4a045",children:"O que \xE9 Big O Notation?"})}),` `,(0,n.jsx)(e.li,{children:(0,n.jsx)(e.a,{href:"https://www.geeksforgeeks.org/bubble-sort-algorithms-by-using-javascript/",children:"Bubble Sort algorithm using JavaScript"})}),` `,(0,n.jsx)(e.li,{children:(0,n.jsx)(e.a,{href:"https://brasilescola.uol.com.br/o-que-e/matematica/o-que-e-logaritmo.htm",children:"O que \xE9 logaritmo"})}),` `,(0,n.jsx)(e.li,{children:(0,n.jsx)(e.a,{href:"https://dev.to/vapordev/complexidade-logaritmica-o-log-n-3n86",children:"Complexidade Logar\xEDtmica O(log n)"})}),` `,(0,n.jsx)(e.li,{children:(0,n.jsx)(e.a,{href:"https://stackabuse.com/merge-sort-in-javascript/",children:"Merge Sort in JavaScript"})}),` `]})]})}function y(t={}){let{wrapper:e}=t.components||{};return e?(0,n.jsx)(e,Object.assign({},t,{children:(0,n.jsx)(c,t)})):c(t)}var B=y;return b(x);})(); ;return Component;

‌‌‌

Mocker API Faster

Shortcut Keys

‌

‌
‌
‌