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));
    }
}
Improve this question
7
  • 5
    Storing the result of findmin(a,(n-1)); instead of calling it again would help. Commented Apr 26, 2018 at 2:33
  • goto last index of array by recursion. Let last element be the minimum element and return it. At each unfolding recursion compare current index element with answer min and update if necessary. Commented Apr 26, 2018 at 2:35
  • @John3136 I'm surprised how much of a difference that made, it seems to be running at linear complexity now. Commented Apr 26, 2018 at 2:51
  • 1
    if n represents size, your algo is wrong (a[0] should not be valid when n == 0, else you don't check a[n]). Commented Apr 26, 2018 at 3:07
  • use a heap data struct. findMin() is O(1) Commented Apr 26, 2018 at 4:15

2 Answers 2

Reset to default
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);
}
Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

does this create a copy O(n - 1) times too?
@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.
@codekaizer - "Decay" sounds better than "type rot".
@codekaizer - Take your pick, but end up here: stackoverflow.com/questions/1461432/…
@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.
|
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.

Improve this answer

19 Comments

@GRG This is homework question or assignment. Writing answer is not the ways of helping. Please guide him the way
@BrijRajKishore - On some occasions, writing the answer might teach a student not to trust code from the internet. :-)
@BrijRajKishore Sometimes an answer is voted to +4, although it is incorrect and O[n^2].
@JiveDadson enlighten me how this algorithm is O(n^2)
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.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.