I'm sure you've heard about ChatGPT by now. AI capable of solving a number of different tasks. In this article, we'll look at how we can use prompting to learn more about a topic. Let's focus on a topic feared by many computer science students, Big O notation, how to calculate time complexity in algorithm. Enough from me, lets hear from the AI using nothing but prompts :)
Let's take on the mindset of a student.
References
So they tell you, you need to learn Big O notation, or "the Big O no" as they said in my days
You sit in front of an Open AI interface using nothing but prompts. Let's try prompting. I heard from my professor there are different complexity levels, n and n^2 with n^2 being worse:
> # show me code with O(n^2) complexity
def find_duplicates(arr):
duplicates = []
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] == arr[j]:
duplicates.append(arr[i])
return duplicates
ok, loop in a loop, that does look like it could take time. How about n ?
> # rewrite above code as O(n) complexity
def find_duplicates(arr):
duplicates = set()
seen = set()
for num in arr:
if num in seen:
duplicates.add(num)
else: seen.add(num)
return duplicates
ok, a loop less, that does seem simpler to look at. But can I trust what it's giving me, lets ask:
> # what is the O(n) complexity of above code?
O(n)
ok, seems to work. I have a confession to make, I don't really know about coding. Let's see if I can have things explained to me:
> # describe the above code
The above code is a function that takes in an array as an argument and returns a set of any duplicate values that appear in the array. It does this by first creating two empty sets, one to store the duplicates and one to store the values that have already been seen. It then iterates through the array, checking if the current value is already in the seen set. If it is, it adds it to the duplicates set. If not, it adds it to the seen set. Finally, it returns the duplicates set.
ok, but can I make sure this is the best solution?
> # rewrite above code to be more efficient
def find_duplicates(arr):
duplicates = set()
seen = {}
for num in arr:
if num in seen:
seen[num] += 1
if seen[num] > 1:
duplicates.add(num)
else:
seen[num] = 1
return duplicates
Amazing !
Final question tell me about Big O notation:
> # describe how you calculate Big O notation of below code line by line
def find_duplicates(arr):
duplicates = set()
seen = {}
for num in arr:
if num in seen:
seen[num] += 1
if seen[num] > 1:
duplicates.add(num)
else:
seen[num] = 1
return duplicates
# Line 1: O(1)
# Line 2: O(1)
# Line 3: O(1)
# Line 4: O(n)
# Line 5: O(1)
# Line 6: O(1)
# Line 7: O(1)
# Line 8: O(1)
# Overall: O(n)
Ok, great, think I've learned something today, that I don't need coding, or do I? ;)
Summary
we were able to have the AI explain the code for us, both in terms of complexity and what it does line by line. This can be used both by teachers that want to create a course and student learning a task.
