Optimizing Algorithm Complexity with ChatGPT

Before we dive into using chatGPT for optimization, let's first understand algorithm complexity, it refers to the efficiency of a procedure used for solving a problem or performing a computation in terms of both time and memory usage. Time complexity it's the time taken by an algorithm to complete, while space complexity is the amount of memory it requires to run. We generally want to cut both time and space complexity to make our algorithms as efficient as possible.

Identifying Areas for Optimization

To start identifying areas for optimization in your code. Look for loops or recursive functions that are consuming a lot of time or memory. These are the areas where optimization can make the biggest impact.

Using GPT to Optimize Algorithms

Now that you've identified areas for optimization, you can use GPT to help optimize your algorithms. One way to do this is by using GPT to generate alternative algorithms with lower time or space complexity. Provide chatGPT with a description of your algorithm and ask it to generate alternative algorithms that achieve the same result but with lower complexity.

The following TypeScript function with a complexity of O(n^2) that we can reduce to O(n):

const reduceAssetList = (assetList: AssetList[]) => {
? let reducedAssetList
? for (const asset of assetList) {
? ? if (reducedAssetList) {
? ? ? for (let index = 0; index < reducedAssetList.length; index++) {
? ? ? ? if (
? ? ? ? ? asset.policy_id === reducedAssetList[index].policy_id &&
? ? ? ? ? asset.asset_name === reducedAssetList[index].asset_name
? ? ? ? ) {
? ? ? ? ? reducedAssetList[index] = {
? ? ? ? ? ? ...reducedAssetList[index],
? ? ? ? ? ? quantity: `${
? ? ? ? ? ? ? Number.parseInt(reducedAssetList[index].quantity) +
? ? ? ? ? ? ? Number.parseInt(asset.quantity)
? ? ? ? ? ? }`,
? ? ? ? ? }
? ? ? ? }
? ? ? }
? ? } else {
? ? ? reducedAssetList = [asset]
? ? }
? }
? return reducedAssetList
}        

The reduceAssetList function is designed to take an array of AssetList objects as input and reduce them based on the values of two properties, policy_id and asset_name. It does this by iterating over each AssetList object in the input array and checking whether a matching object already exists in the reduced output array. If a match is found, the function updates the quantity property of the matching object by adding the quantity property of the input object to it. If no match is found, the input object is added to the reduced output array.

We have two loops one inside the other one which makes the complexity O(n^2), but we can do better, In this case, I didn't even have to explain what the function does I just asked chatGPT

"Here is a typescript function with a complexity of O(n^2), can you optimize it"

Then I got the response with a nice explanation

Testing and Refining

It's important to note that GPT answers aren't always trustworthy. Its responses are based on patterns in the text it was trained on, not on external facts and data. That's why it's crucial to have the know-how and the skills to confirm the responses, in this case by conducting thorough testing to ensure that it produces the expected results. This may involve running various test cases with different input data and checking if the output is correct.

Conclusion

In conclusion, chatGPT can be a powerful tool for optimizing algorithm complexity and improving your skills as a developer, however, at least basic knowledge is required to be able to validate the code and test it, this is one of the reasons why AI won't replace developers but it will make them better and more efficient.