0

Stooge sort is a recursive sorting algorithm and it doesn't use any temp arrays. So why is the space complexity O(n) and not O(1)?

def stoogesort(arr, l, h): 
    if l >= h: 
        return

    # If first element is smaller 
    # than last, swap them 
    if arr[l]>arr[h]: 
        t = arr[l] 
        arr[l] = arr[h] 
        arr[h] = t 

    # If there are more than 2 elements in 
    # the array 
    if h-l + 1 > 2: 
        t = (int)((h-l + 1)/3) 

        # Recursively sort first 2 / 3 elements 
        stoogesort(arr, l, (h-t)) 

        # Recursively sort last 2 / 3 elements 
        stoogesort(arr, l + t, (h)) 

        # Recursively sort first 2 / 3 elements 
        # again to confirm 
        stoogesort(arr, l, (h-t))

Does the recursion have something to do with the space complexity of O(n)?

Nehemiah Britt
  • 99
  • 1
  • 4
  • Try running the algorithm on an array of size 100 and 100000000; do they take the same amount of time or significantly different amounts of time? If the time is different it is proportional to the length, if it is the same it is constant time. – vandench Feb 02 '19 at 20:25
  • OP is talking about space complexity, as in how much memory is used. Since stoogesort's only modification is a swap of array locations, one would think each recursive call would only need extra space for the temp `t` of the swap. – glumplum Feb 02 '19 at 22:58
  • This post should probably help OP figure it out. https://stackoverflow.com/questions/43298938/space-complexity-of-recursive-function – glumplum Feb 02 '19 at 23:02

0 Answers0