Big O() of recursive algorithm for finding minimum number

Question

I have following code I was told findmin is O(n^2), but I cannot see it.

#include <iostream>
#include <cstdlib>
#include <ctime>

int findmin(const int a[], int n);
int cnt = 0;

int main (void)
{
    int num = 100;
    std::srand(std::time(nullptr));

    int arr[num];
    for (int i = 0; i < num; ++i)
        arr[i] = std::rand() % num;

    findmin(arr, num);
    std::cout << cnt;
    return 0;
}

int findmin(const int a[], int n)
{
    cnt++;
    if(n == 0)
        return a[0];

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

In my mind this algorithm goes down the last element, grabs it and comes back from recursion, compares it to an element and goes on, thus in my mind this is O(2*n).

In another way if we have array 3, 5, 7, 1, 2, 6, recursively we go down and grub 6. On our way up we find that 2 is smaller than 6 so we grub 2. Than we go up and compare it to 1 grub 1 and go up, comparing it to 7, 5, 3. So that is O(n). We are going through array n times. I would really appreciate if somebody can explain this to me.

Here is my source https://stackoverflow.com/a/50034011/5550963

is this code working? findmin(arr,100) will lead to index out of bound in a[n] isn't it? — Alessandro Teruzzi, Apr 26 '18 at 16:34

score 2 · Answer 1 · answered Apr 26 '18 at 16:33

2

O(n) ⊂ O(n^2) ∧ t(n) ∈ O(n) => t(n) ∈ O(n^2)

Yes, findmin is O(n), but it it is therefore also O(n^2).

answered Apr 26 '18 at 16:33

Ext3h

5,713
17
43

score 0 · Accepted Answer · edited Apr 26 '18 at 16:26

0

It is O(n). Whoever told you otherwise is mistaken.

edited Apr 26 '18 at 16:26

Drew Dormann

59,987
13
123
180

answered Apr 26 '18 at 16:18

Blindy

65,249
10
91
131

2

Except that O(n^2) is a superset of O(n). So whoever told him was correct, just not as precise as possible. – Ext3h Apr 26 '18 at 16:21
@Ext3h Please could you elaborate. – Apr 26 '18 at 16:24
1

That guy doesn't know what he's talking about. "That's it. I'm done." is their battle cry when faced with proof they're wrong. – Blindy Apr 26 '18 at 19:29

Big O() of recursive algorithm for finding minimum number

2 Answers2