Students, fear not, even Big O notation is something AI can help explain
Published Apr 01 2023 12:00 AM 1,546 Views
Microsoft
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[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.
Co-Authors
Version history
Last update:
‎Apr 01 2023 12:00 AM
Updated by: