3

I have an assignment for a c++ programming class to write a recursive function without the use of static variables, with the following prototype: int findmin(const int a[], int n);

My solution works (for very small arrays), however I think ~2^n complexity is excessive and could be improved.

Are there any improvements that could be made within the specified criteria that would make this more efficient? 

int findmin(const int a[], int n)
{
    if(n == 0)
        return a[0];
    else
    {
        if(a[n-1] < findmin(a,(n-1)))
            return a[n-1];
      else
            return findmin(a,(n-1));
    }
}
Brian
  • 31
  • 1
  • 3

2 Answers2

4

It's a little silly to worry about efficiency, given that there is an obvious, non-recursive way to do it in O(n), one pass. There is even an STL algorithm std::min_element. But then, it's a silly assignment. FIrst be sure your solution is correct. When n==0, will a[0] be valid? Generally, such an n indicates the length of the array, not the lowest index.

To go from O[n^2] to O[n], be sure to compare each element only once. That implies not starting at the beginning of the array on every pass.

#include <algorithm>
#include <cassert>

int findmin(const int a[], int n)
{
    assert(n>0);
    if(n == 1)  // See heyah.
        return a[0];
    else
    {
        return std::min(a[0], findmin(a + 1, n - 1));
    }
}

In for-real C++ code, if for some reason we were saddled with the old fashion function signature, we would do something like this:

int findmin(const int a[], int n) {
    if(n<=0) { throw std::length_error("findmin called on empty array");}
    return *std::min_element(a, a+n);
}
Jive Dadson
  • 16,680
  • 9
  • 52
  • 65
  • does this create a copy `O(n - 1)` times too? – Joseph D. Apr 26 '18 at 04:14
  • 2
    @codekaizer. It creates no copies at all. The signature `const int a[]` is a holdover from C. We don't do that anymore. (C++ newbies should not even know about it yet, but that's another rant.) The array declaration `a[]` "decays" to a pointer, `int *a`. – Jive Dadson Apr 26 '18 at 04:18
  • 1
    @codekaizer - "Decay" sounds better than "type rot". – Jive Dadson Apr 26 '18 at 04:22
  • so if I search in the C++ specs the correct terminology is "type rot"? or "pointer decay"? – Joseph D. Apr 26 '18 at 04:23
  • 1
    @codekaizer - Take your pick, but end up here: https://stackoverflow.com/questions/1461432/what-is-array-decaying#1461449 – Jive Dadson Apr 26 '18 at 04:30
  • @JiveDadson. I was thinking this solution in java. But in C++ it makes a whole lot difference what n indicates. In java array size is implicit but in C++ there is a whole different story. Impressive.detail catch. – Brij Raj Kishore Apr 26 '18 at 04:42
  • 4
    @BrijRajKishore - Things are even better in C++ than in Java, provided one does things the easy way(s). Problem is, instructors teach students to write C code to be compiled with a C++ compiler. There are a lot of features in C++ that, for reasons of backward compatibility, are held over from C. – Jive Dadson Apr 26 '18 at 04:46
  • @JiveDadson can you suggest some links where I can study in detail what you saying above? – Brij Raj Kishore Apr 27 '18 at 01:51
3

You could do conditional operator ?: to get rid of bunch if else statements, to make function cleaner. And instead of calling findmin() twice you could assign return value to variable inside of the statement, this is main advantage of this code vs. original one.

int findmin(const int a[], int n) {
   if (n == 0) // base case
      return a[0];

   return a[n] < (int min = findmin(a, n - 1)) ? a[n] : min;
}

This (a[n] < (int min = findmin(a, n - 1)) ? a[n] : min;) could be done using if statement as well:

if (a[n] < (int min = findmin (a, n - 1))
     return a[n];
else
     return min;

EDIT: Per many reputable sources, this is O(n) time. O (n^2) would be if we are comparing each element with all the other elements.

  • 4
    @GRG This is homework question or assignment. Writing answer is not the ways of helping. Please guide him the way – Brij Raj Kishore Apr 26 '18 at 02:39
  • This is good pseudocode for the right algorithm but it's got some typos. I guess that's one way to make the asker think? – hegel5000 Apr 26 '18 at 02:44
  • @BrijRajKishore I hope you are happy :) –  Apr 26 '18 at 02:49
  • @hegel5000 :) not anymore :) –  Apr 26 '18 at 02:51
  • That is not "the right algorithm". It is O[n^2], the evil from which we flee. – Jive Dadson Apr 26 '18 at 03:42
  • 2
    @BrijRajKishore - On some occasions, writing the answer might teach a student not to trust code from the internet. :-) – Jive Dadson Apr 26 '18 at 03:54
  • 1
    @BrijRajKishore Sometimes an answer is voted to +4, although it is incorrect and O[n^2]. – Jive Dadson Apr 26 '18 at 04:07
  • 2
    @JiveDadson enlighten me how this algorithm is O(n^2) – Brij Raj Kishore Apr 26 '18 at 04:24
  • OK guys I will delete this but explain to me how the is this `O(n^2)`?since it goes down recursively `n-1` elements and on its way back compares it to only one element? So in `a[n]` is `O (1)` and findmin(a, n - 1) is `O (n)`? –  Apr 26 '18 at 04:27
  • @BrijRajKishore n+(n-1)+(n-2)+(n-3)+...1 – Jive Dadson Apr 26 '18 at 04:27
  • It needs to increment a as it decrements n. See the answer I posted. – Jive Dadson Apr 26 '18 at 04:28
  • What do you mean by increment a? –  Apr 26 '18 at 04:31
  • @GRC, it means `a[prev] < a[prev + 1]` should have been previously solved by the previous iteration. to make it `O(n)` you should have atleast "memoized" the previous results via Dynamic Programming. – Joseph D. Apr 26 '18 at 04:33
  • It's the a+1 in `return std::min(a[0], findmin(a + 1, n - 1));` or `return std::min(a[0], findmin(&(a[1]), n - 1));` if you're not into the whole brevity thing. – Jive Dadson Apr 26 '18 at 04:33
  • I still do not get it but OK, I believe you. For me this is like having a ball with numbers on staircase, you go down the staircase pick the ball on the bottom, than as you go upstairs you take a look at the ball at the stair you are on, if it is lesser, you drop ball from your hand and grub the one on that stair. So you are not going down the stairs again. You are not doing bubble sort and finding the next minimum. –  Apr 26 '18 at 04:45
  • in other words you are not comparing every ball with every other ball, you are comparing 1 ball (ball in you hand) with n - 1 other balls. –  Apr 26 '18 at 04:49
  • 1
    O(n^2) does not mean the steps number exactly n^2. (n^2-n)/2 is O(n^2). Figure it out. Step through the algorithm and count. Turn that counting process into a mathematical series. Have fun. I'm done. – Jive Dadson Apr 26 '18 at 04:56
  • Well lets say you have 3, 5, 7, 1, 2, 6. Recursively you go down 6 steps and grab 6. On your way back up you compare it to 2, grab 2, compare it to 1, grab 1, compare it to 7, 5, 3. That is 6 steps up, you do not care about 2 and 6 anymore. So that is 2 * n, not n + (n-1) ... 1. –  Apr 26 '18 at 05:00
  • And I do know that 0(n^2 - n) means 0 (n^2). –  Apr 26 '18 at 05:06