### Thread: Space complexity of recursive function

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. Well, it is recursive, but it appears to be O(N), not O(log(N))
3. 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.)
Last edited by b49P23TIvg; January 23rd, 2013 at 11:43 AM.
4. 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?
5. 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. 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?
7. 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. 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?
9. 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. 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. 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?
12. a+n/2 is the same as
&a[n/2]

This might help.