Big-O help

jtrackers (4)
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.
1
2
3
4
5
6
 
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)?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
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:

1
2
3
4
5
6
7
8
9
10
 
int main() {
  int a[4] = {5, 3, 2, 7};

  sort(a, 4);

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

 return 0;
}
Registered users can post here. Sign in or register to post.

C++

Forum