Big-O help

[jtrackers]

I was wondering if someone could help me out finding the Big-O of these two functions:

This function I'm guessing is O(1) but I'm thinking that's wrong.

int sum(int A[], int i, int n) {
  if (n == 1)
    return A[i];

  return sum(A, i, n/2) + sum(A, i + n/2, (n+1)/2);
}

I need the Big-O of the sort function for this one: I'm guessing it's O(n)?

void swap(int& a, int& b) {
  int temp = a;
  a = b;
  b = temp;
}

void swapMin(int A[], const int& index) {
  int indexMin = index;
  for (int i = index-1; i >= 0; --i)
    if (A[i] < A[indexMin])
      indexMin = i;

  swap(A[index], A[indexMin]);
}

void sort(int A[], int n) {
  for (int i = n-1; i >= 0; --i)
    swapMin(A, i);
}

Also, could someone tell me the output of this, using the above functions:

int main() {
  int a[4] = {5, 3, 2, 7};

  sort(a, 4);

  for (int i = 0; i < 4; ++i)
    cout << a[i] << " ";

 return 0;
}

[coder777]

Big O is basically a mathematical series:

http://en.wikipedia.org/wiki/Series_%28mathematics%29

To understand what series you have I recommend to count the iterations of the loop (that basically what Big O is all about):

#include <iostream>
using namespace std;

int count = 0; // Note

void swap(int& a, int& b) {
  int temp = a;
  a = b;
  b = temp;
}

void swapMin(int A[], const int& index) {
  int indexMin = index;
  for (int i = index-1; i >= 0; --i)
  {
      ++count; // Note
    if (A[i] < A[indexMin])
      indexMin = i;
}
  swap(A[index], A[indexMin]);
}

void sort(int A[], int n) {
  for (int i = n-1; i >= 0; --i)
    swapMin(A, i);
}

int main() {
  int a[4] = {5, 3, 2, 7};

  sort(a, 4);

  for (int i = 0; i < 4; ++i)
    cout << a[i] << " ";

    cout << endl << "count = "  << count << endl; // Note

 return 0;
}

Try this for different sizes of the array a (5,6,7,8...)

You will see that the value of count will follow a certain schematic. Tip: How many 4/2, 5/2, ... n/2 are there?
And no it's not O(n) (EDIT: it's (n² - n) / 2)

[armonsafai]

sort function is O( n^2)

[htirwin]

int sum(int A[], int i, int n) {
  if (n == 1)
    return A[i];

  return sum(A, i, n/2) + sum(A, i + n/2, (n+1)/2);
}

T(1) = 1

T(n) = 2T(n/2) + 1
= 2*( 2T(n/4) + 1 ) + 1
= 2^kT(n/2^k) + k

Now you want to eliminate T( n/2^k) by substituting the value for K that makes it T(1). ...