January 23rd, 2013, 09:07 AM

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=n1;
if(n==1  n==0) return 1;
if(a[check]<a[check1])return 0;
else return(is_sorted(a,n1));
}
if not. can anyone propose how to meet those demands?
January 23rd, 2013, 09:30 AM

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
January 23rd, 2013, 10:33 AM

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!
January 23rd, 2013, 11:07 AM

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

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!
January 23rd, 2013, 11:45 AM

January 23rd, 2013, 12:40 PM

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!
January 23rd, 2013, 12:57 PM

first of all thanks,it works perfectly...can you please explain why?
January 23rd, 2013, 02:58 PM

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!
January 23rd, 2013, 06:26 PM

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
January 24th, 2013, 12:40 AM

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?
January 24th, 2013, 08:35 AM

a+n/2 is the same as
&a[n/2]
This might help.
[code]
Code tags[/code] are essential for python code and Makefiles!