Space complexity of recursive function

Dev Shed Forums Sponsor:

January 23rd, 2013, 09:07 AM

daniig

Registered User

Join Date: Jan 2013

Posts: 9

Time spent in forums: 2 h 30 m 42 sec
Reputation 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?

January 23rd, 2013, 09:30 AM

Scorpions4ever

Banned ;)

Dev Shed God 9th Plane (9000 - 9499 posts)

Join Date: Nov 2001

Location: Woodland Hills, Los Angeles County, California, USA

Posts: 9,387

Time spent in forums: 1 Month 4 Weeks 1 Day 21 h 39 m 3 sec
Reputation Power: 4080

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

January 23rd, 2013, 10:33 AM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,371

Time spent in forums: 1 Month 2 Weeks 3 Days 11 h 35 m 33 sec
Reputation Power: 383

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.)

__________________
[code]Code tags[/code] are essential for python code!

Last edited by b49P23TIvg : January 23rd, 2013 at 11:43 AM.

January 23rd, 2013, 11:07 AM

daniig

Registered User

Join Date: Jan 2013

Posts: 9

Time spent in forums: 2 h 30 m 42 sec
Reputation 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?

January 23rd, 2013, 11:42 AM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,371

Time spent in forums: 1 Month 2 Weeks 3 Days 11 h 35 m 33 sec
Reputation Power: 383

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.

January 23rd, 2013, 11:45 AM

daniig

Registered User

Join Date: Jan 2013

Posts: 9

Time spent in forums: 2 h 30 m 42 sec
Reputation Power: 0

ok so how is it done?

January 23rd, 2013, 12:40 PM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,371

Time spent in forums: 1 Month 2 Weeks 3 Days 11 h 35 m 33 sec
Reputation Power: 383

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.

January 23rd, 2013, 12:57 PM

daniig

Registered User

Join Date: Jan 2013

Posts: 9

Time spent in forums: 2 h 30 m 42 sec
Reputation Power: 0

first of all thanks,it works perfectly...can you please explain why?

January 23rd, 2013, 02:58 PM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,371

Time spent in forums: 1 Month 2 Weeks 3 Days 11 h 35 m 33 sec
Reputation Power: 383

Quote:

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.

#10

January 23rd, 2013, 06:26 PM

Scorpions4ever

Banned ;)

Join Date: Nov 2001

Location: Woodland Hills, Los Angeles County, California, USA

Posts: 9,387

Time spent in forums: 1 Month 4 Weeks 1 Day 21 h 39 m 3 sec
Reputation Power: 4080

Quote:

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}

#11

January 24th, 2013, 12:40 AM

daniig

Registered User

Join Date: Jan 2013

Posts: 9

Time spent in forums: 2 h 30 m 42 sec
Reputation 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?

#12

January 24th, 2013, 08:35 AM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,371

Time spent in forums: 1 Month 2 Weeks 3 Days 11 h 35 m 33 sec
Reputation Power: 383

a+n/2 is the same as
&a[n/2]

This might help.

Space complexity of recursive function

Developer Shed Advertisers and Affiliates