0

Ok, I am trying to understand the concept of Big O. I have a function I am suppose to find the Big O and I am not quite "getting it" this is an example in the book of one that is like my homework.. I know the answer is O(nk) but can someone please break this down in simplistic terms so I might better understand. 

int selectkth(int a[], int k, int n)
{
int i, j, mini, tmp;
for (i=0; i < k; i++)
{
mini = i;
for (j = i+1; j < n; j++)
{
if (a[j] < a[mini])
mini = k;
tmp = a[i];
a[i] = a[mini];
a[mini] = tmp;
}
}
return a[k-1];
}
Gavon Black
  • 33
  • 1
  • 1
  • 4
  • Checking the number of loops might help guide you in getting closer to an accurate measure of complexity... but as a better (and probably more accurate) reference, I'd suggest taking a look at this other [question/answer](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) (and in particular, [this answer](http://stackoverflow.com/a/4852666/1167750).) :) – summea Apr 09 '13 at 23:46

1 Answers1

1

When calculating the bigO try to think of the worst time complexity, and pay attention to loops. Here we have two loops:

// Below line is run k times

for (i=0; i < k; i++)

// Worst case scenario, loop below will run n times.

for (j = i+1; j < n; j++)

bigO would be these two values multiplied togehter = k*n

Also check out this post: What is a plain English explanation of "Big O" notation?

Community
  • 1
  • 1
Ali
  • 26
  • 2