AI Code Review - Optimized Problem Solving

In the first part of AI code review series, I did a review of basic problem solving skills of ChatGPT and Google Bard. In today's post, I will review the optimized problem solving capabilities.

Both ChatGPT and Google Bard were prompted with optimizations of simple algorithms.

Problem 1: Optimization capability based on trade-off between time and space complexity

In my opinion, it's impossible to reduce time complexity without increasing space complexity and vice a versa. Both are inversely proportional and there's always a trade-off between these two. I wanted to review this capability and prompted below question.

Prompt: Can you send me the most efficient solution to check if array contains any two numbers that adds to a given sum?

For this problem, both ChatGPT and Google Bard were able to provide optimized solution by eliminating one iteration on the main array and reducing time complexity/increasing space complexity. The key difference is Google Bard used a HashTable and ChatGPT used a Set. In case of HashTable, the lookup complexity is a constant and always O(1) whereas a Set can take up to O(n). Considering this, Google Bard is a winner in this problem.

In summary, both the platforms were able to reduce time complexity by increasing the space complexity. However, the data structure chosen by Google Bard is better than ChatGPT.

Problem 2: Optimization capability based on input restriction

I am sure that depending on the input restrictions, there's always a better solution for the specific case. For e.g, if there's a condition on the input array that it can include only numbers in some sequence or only even or odd numbers, then it's possible to find the sum without any iteration using simple mathematics. I wanted to review this capability and prompted questions accordingly.

While both ChatGPT and Google Bard weren't able to provide a solution for this, ChatGPT is a partial winner in this problem. ChatGPT had some extra information saying why it's impossible to do without iteration and suggested that using in-built functions can reduce the code but still involves iteration in the library function. It had no idea about optimization based on specific inputs using mathematics. Google Bard confidently gave a code using some mathematics which failed to find the correct sum for the example input given in code itself. 

The complete python code generated by Google Bard is given below which outputs incorrect sum for the example input that is auto generated. I assume that Google Bard tried to use the formula for sum of first n odd numbers, so including the missing '3' should make it work. However, even if that's the case n^2 is a better formula as the order of numbers doesn't matter if we use  n^2.

Conclusion

I had the intention of extending this code review series for real time applications and machine learning solutions. However, I would say AI generated code is great for self study and understanding, but not suitable for generating code with proper validations and cannot adapt to dynamic requirements at this point in time. Hence, I will wait for more updates to these platforms before further reviews.