Students, fear not, even Big O notation is something AI can help explain

[Guest Chris_Noring]

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

- If you want to try this on your own, try signing up to Azure Open AI What is Azure OpenAI Service? - Azure Cognitive Services | Microsoft Learn

- Copilot is another interesting choice, GitHub Copilot · Your AI pair programmer · GitHub

 

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 == arr[j]:

duplicates.append(arr)

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.

 

Continue reading...