Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
January 23rd, 2013, 10: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?

#2
January 23rd, 2013, 10:30 AM
 Scorpions4ever
Banned ;)

Join Date: Nov 2001
Location: Woodland Hills, Los Angeles County, California, USA
Posts: 9,534
Time spent in forums: 2 Months 3 Days 5 h 3 m 14 sec
Reputation Power: 4106
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

#3
January 23rd, 2013, 11:33 AM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,132
Time spent in forums: 1 Month 3 Weeks 2 Days 5 h 47 m 38 sec
Reputation Power: 455
Every element must be examined! Therefore the algorithm must be O(n) or worse. 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 12:43 PM.

#4
January 23rd, 2013, 12:07 PM
 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?

#5
January 23rd, 2013, 12:42 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,132
Time spent in forums: 1 Month 3 Weeks 2 Days 5 h 47 m 38 sec
Reputation Power: 455
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.

#6
January 23rd, 2013, 12:45 PM
 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?

#7
January 23rd, 2013, 01:40 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,132
Time spent in forums: 1 Month 3 Weeks 2 Days 5 h 47 m 38 sec
Reputation Power: 455
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.

#8
January 23rd, 2013, 01: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?

#9
January 23rd, 2013, 03:58 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,132
Time spent in forums: 1 Month 3 Weeks 2 Days 5 h 47 m 38 sec
Reputation Power: 455
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, 07:26 PM
 Scorpions4ever
Banned ;)

Join Date: Nov 2001
Location: Woodland Hills, Los Angeles County, California, USA
Posts: 9,534
Time spent in forums: 2 Months 3 Days 5 h 3 m 14 sec
Reputation Power: 4106
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, 01: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, 09:35 AM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,132
Time spent in forums: 1 Month 3 Weeks 2 Days 5 h 47 m 38 sec
Reputation Power: 455
a+n/2 is the same as
&a[n/2]

This might help.

 Viewing: Dev Shed Forums > Programming Languages > C Programming > Space complexity of recursive function