0
#include <iostream>

int find_smallest(int a[], int l, int r){
    if (l ==r)
        return a[l];
    else if (l+1 == r)
        return ((a[l] < a[r]) ? a[l] : a[r]);
    else {
        int m = (l + r) / 2;
        int d1 = find_smallest(a, l, m);
        int d2 = find_smallest(a, m+1, r);
        return  ((d1 < d2) ? d1 : d2);
    }
}

int main(){
    int a[] = {5,3,2,5,6,7};
    std::cout << find_smallest(a, 0, 5);
}

This is a code to find the smallest element in an array. I have taken a 6 element array just for testing purpose but how should I analyze the Big-O complexity of the program?

NathanOliver
  • 171,901
  • 28
  • 288
  • 402
Vedant
  • 27
  • 3
  • Are you asking how to time this function or how to get the big-O complexity of it? – NathanOliver Apr 22 '19 at 16:55
  • Big O complexity. – Vedant Apr 22 '19 at 16:58
  • One way is to place a counter that sums up the iterations and run the algorithm for various input sizes (I find doubling the size of the input each time to be very helpful). Compare the rate of increase of the number of iterations vs the size of the input. Plotting iterations vs input size so you can look at the curve also helps. – user4581301 Apr 22 '19 at 17:05
  • 1
    "Runtime analysis: How do I evaluate the runtime of the code?" - You write a benchmark program and run it. – Jesper Juhl Apr 22 '19 at 17:09
  • ***You write a benchmark program and run it.*** Be careful with this you could easily get the wrong results. Make sure you have optimizations enabled. And at the same time that you code is not totally optimized out. Also make sure that your algorithm runs for long enough to time. If it runs in a very short time ( 1ms ) the time measured may be highly influenced by your OS and its activity. – drescherjm Apr 22 '19 at 17:21

1 Answers1

1

This is actually O(n) - To find out why you have to analyze the recursion tree of your algorithm and how many operations are made at each step.

Analyzing the number of operations is simple, you do a simple comparison between two terms so that is O(1), now we need to figure out how many times the recursive function is called.

Turns out that is also simple, you call find smallest for the entire left and right subarray, so at first you have 1 comparison, then you have 2, then 4, until you have n comparisons.

n + n/2 + n/4 ... = 2*n = O(n)

hbejgel
  • 4,674
  • 2
  • 17
  • 27
  • In the other answer I saw your comment about wanting to find smallest out a sorted array inverted at a pivot point in O(log n) - In order to do that you'd first need to find that pivot point (which takes Ologn) and then do a binary search on either of the subarrays (which takes another Ologn). O(2*logn) = O(logn) – hbejgel Apr 22 '19 at 17:44