Calculating Big O

Question

I am new to programming and I am trying to figure out how to calculate the Big O of algorithms. For example:

int selectkth(int a[], int k, int n){
    int i, j, mini, temp;
    for(i=0, i < k, i++){
      mini = i;
      for(j = i+1; j < n; j++)
       if(a[j] < a[mini])
         mini = j;
         temp = a[i];
         a[i] = a[mini];
         a[mini] = temp;
         }
      return a[k-1];
    }

I know there are 9 steps taking place here and that the nested loops are supposed to be multiplied together. I got O(n^2) when I first attempted but I don't think that is correct. Can someone explain how to properly calculate Big O in a simplified way for a rookie like me? Any explanation will help or examples of your own. Thanks :)

check my answer sorry i put a comment by mistake – Jean Raymond Daher Oct 07 '14 at 06:19 — Jean Raymond Daher, Oct 07 '14 at 06:19

score 0 · Answer 1 · answered Oct 07 '14 at 06:21

o(n^2) is correct . biggest factor in running time in your code are the two nested loops. the other stuff is just handling variables - which you don't need to worry about . the Big O here is actually kn=nn=n*2=O(n^2) it is the length of the arrays . k times n .

score 0 · Answer 2 · answered Oct 07 '14 at 06:33

For outer loop, there k iteration
for inner loop: 
For iteration #1 : n  times array manipulation
For iteration #2 : n - 1 times array manipulation
.
.
For iteration #k : n - k times array manipulation

total array manipulation = n + (n-1) + ..... + (n -k)
= n(n+1) / 2 - k(k+1) /2
=~(n*2 - k*2)

= ~(n*2) // if n is very very greater than k

Calculating Big O

2 Answers2