#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    9
    Rep Power
    0

    Space complexity of recursive function


    Hi,

    this function has to check if an array is not descending it has to be recursive and it's space complexity has to be O(log(n))
    does it meet these requirements?
    Code:
    int is_sorted(int a[ ], int n)
    {
        int check=n-1;
        if(n==1 || n==0) return 1;
        if(a[check]<a[check-1])return 0;
        else return(is_sorted(a,n-1));
    }
    if not. can anyone propose how to meet those demands?
  2. #2
  3. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,593
    Rep Power
    4207
    Well, it is recursive, but it appears to be O(N), not O(log(N))
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  4. #3
  5. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,709
    Rep Power
    480
    Every element must be examined! Therefore the algorithm must be O(n) or worse. [edit]O(n) time complexity. The problem statement specifies SPACE complexity. This is possible.[/edit]

    (Or show my logic error.)
    Last edited by b49P23TIvg; January 23rd, 2013 at 11:43 AM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    9
    Rep Power
    0
    so this is a HW assignment and after asking they say there is a way to make it's space complexity O(log(n)). any ideas on how?
  8. #5
  9. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,709
    Rep Power
    480
    Oh, space complexity, not time complexity.

    Sure, and since the algorithm must be recursive it's important to keep the space complexity small.

    An O(log(n)) space complexity algorithm divides intervals in half.
    [code]Code tags[/code] are essential for python code and Makefiles!
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    9
    Rep Power
    0
    ok so how is it done?
  12. #7
  13. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,709
    Rep Power
    480
    Code:
    int is_sorted(int a[ ], int n) {
      if (n < 2) return 1;
      if (2 == n) return a[0] <= a[1];
      return is_sorted(a,n/2) && is_sorted(a+n/2,n/2);
    }
    approximately like this. My usual warning applies: my programs don't work the first time and I didn't test this. Certainly could have off by one errors, and certainly could have major logic flaws.
    [code]Code tags[/code] are essential for python code and Makefiles!
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    9
    Rep Power
    0
    first of all thanks,it works perfectly...can you please explain why?
  16. #9
  17. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,709
    Rep Power
    480
    Originally Posted by daniig
    first of all thanks,it works perfectly...can you please explain why?
    Are you quite sure you tried it with ordered and unordered lists of length prime number? Like 17.
    Sprinkle some useful diagnostic print statements and I'm sure you'll figure out why it works or not. To help with the diagnostics, rewrite as
    Code:
    int is_sorted(int a[], int n,int level) {
      /* useful print statement here, include level */
      if (n < 2) return 1;
      if (2 == n) return a[0] <= a[1];
      return is_sorted(a,n/2,level+1) && is_sorted(a+n/2,n/2,level+1);
    }
    and call is_sorted with a known value for level. 0, perhaps.
    [code]Code tags[/code] are essential for python code and Makefiles!
  18. #10
  19. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,593
    Rep Power
    4207
    Originally Posted by daniig
    first of all thanks,it works perfectly...can you please explain why?
    That means you didn't test it all that well. Try and understand what the code is doing and put a few printf() calls to see if you can figure out what's going on.

    HINT: Is {5, 20, 7, 15} sorted or not? How about {5, 20, 7, 34, 15}
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  20. #11
  21. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    9
    Rep Power
    0
    yeah I've actually found other cases it doesn't work that well...but the original "why" was cause i don't understand what the function is doing not why should i check it.
    so 2 questions:
    1. what is it doing?
    2.how to change it so it'll work for all cases?
  22. #12
  23. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,709
    Rep Power
    480
    a+n/2 is the same as
    &a[n/2]

    This might help.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo