Like Tree1Likes
  • 1 Post By iMalc

space complexity of recursive function

This is a discussion on space complexity of recursive function within the C Programming forums, part of the General Programming Boards category; Hi, this function has to check if an array is not descending it has to be recursive and it's space ...

  1. #1
    Registered User
    Join Date
    Jan 2013
    Posts
    1

    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))
    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));
    }
    



    this is what i came up with. i know it's space complexity is O(n) how do i make it O(log(n))?

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,558
    Also here -> Space complexity of recursive function - Dev Shed

    Asking in many places at the same time really annoys people,
    How To Ask Questions The Smart Way
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    The guy who said this got it right:
    "An O(log(n)) space complexity algorithm divides intervals in half."

    Consider the first, middle and last items, then perform two recursive calls. That's all I'm prepared to say.
    stahta01 likes this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Converting recursive function to tail recursive
    By ajacobs365 in forum C Programming
    Replies: 1
    Last Post: 10-30-2011, 08:15 AM
  2. Replies: 1
    Last Post: 12-03-2010, 12:54 AM
  3. Time complexity program/recursive functions
    By XodoX in forum C++ Programming
    Replies: 3
    Last Post: 09-22-2010, 06:26 PM
  4. Make Recursive function 'Tail-Recursive'
    By dp2452 in forum C Programming
    Replies: 7
    Last Post: 12-04-2009, 09:13 AM
  5. Worst-case complexity of this function?
    By Ariod in forum C Programming
    Replies: 3
    Last Post: 08-17-2005, 02:17 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21