I am struggling with Complexity Analysis

[rwill357]

I have been given the task of finding the complexity of the function used to find the kth smallest integer in an unordered array of integers. Below I have displayed the function I am analysizing. I have shown the steps as I understand them. Any help in understanding this would be appreciated.

Outside loop
Initialize i, Initialize j, setting tmp = a, setting a = a[mini], setting a[mini] = tmp, return a[k-1]
Inside Loop 1
Test i<k, Increment i, update mini = i,
Inside Loop 2
Test j < n, Increment j, Test a[j]<a[mini], update mini = j
3k *4n + 6
O(k*n)

[rwill357]

Sorry, I forgot to include the function.

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=j;
            tmp = a[i];
            a[i] = a[mini];
            a[mini] = tmp;
      }
      return a[k-1];

[Anarionist]

first off your missing some declarations I.E(a,k,n) and you dont need this part

a[i] = a[mini];//here you stated a[value of i] equals a[value of mini and before that you said mini =i so the value of i and mini are the same putting them in an array doesnt change anything. :)
a[mini] = tmp;// you really only needed to declare that a[i] =tmp; once again mini has the same value of i;

since mini = i. So you would have two references to the same value which takes up unecessary space ( tmp=a; is fine). also the if statement can go becuase then if statement is always false since j=i+1 so it can never be less than a[mini].

int k;
int n;
int a[50];//just a reference adapt it to suit your needs.

not sure on how to solve it i do know that my above statements should help a bit sorry if they don't i tried. :P

[nezachem]

since mini = i

Indeed? mini may well change by an inner loop. Pay attention to line 6.

Now, regarding complexity. You outer loop executes k times. Right?
Each iteration consists of lines 3, 7, 8 and 9 - their execution time is constant (that is, it doesn't depend of neither n nor k ) - and an inner loop. Right?
The inner loop executes n - i times; each iteration time is at least a time of comparison, and at most a time of comparison plus a time of asignment, which from the complexity perspective is also a constant. Right?

Summing it up, the total time is

Sum{i}[1..k] (const1 + (n - i) * const2)

that is

const1*k + const2*n*k - Sum{i}[1..k](i) * const2

that is

const1*k + const2*n*k - const2*k*k/2

Right?

Again, from the complexity perspective, nobody cares about the linear term. Finally, the complexity estimates as O(n*k - k*k/2). If k is o(n), the second term may also be eliminated, giving O(n*k).

Right?

[Anarionist]

it took me a few minutes to understand but yes logically( from my perspective ) that works for what you want it to.<--ignore this here i will break it down give a few minutes.

[Anarionist]

sorry for double post if it is but i need more room.

here you go read the comments on the code it should help you a bit more.
also if you dont mind me asking is this an assignment from a proffessor or just a simple exercise you wanted to try. I am answering to the best of my abililty so if my answer doesnt suit you or you see a flaw in my evalulation please tell me.

int i, j, mini, tmp; //declare variables

      for (i=0; i<k; i++){ //i =0 while i is less than k increase i
  
      mini = i; // mini = i so i and mini have the same value
 
      for (j = i+1; j < n; j++) //j=value of i+1 while j less than n; increase j
 
      if (a[j]<a[mini]) //if element j is less than element mini of array a then
  
      mini=j; // mini = j so mini and j have same value
   
      tmp = a[i]; // tmp = int array a(int a[ element i])
  
      a[i] = a[mini]; // a[value of i] equals a [value of mini]
  
      a[mini] = tmp; // a[value of mini] equals tmp. which is the same as a[i]=tmp
 
      }
  
      return a[k-1]; // return value of a[value of k-1]
      //based up my second run through of the code i now realize that there isn't any multiplication

oh and i did look at line 6 since and i did cover it. mini cant change because of your assignment in the if statement. The if statement will always be false unless you change it around. the for statement before that you declared j=i+1 well mini=i; so j=mini+1; therefore a[j] cant be less than a[mini] because j will always be one up on i and mini.

[Anarionist]

really really sorry for the triple post but it wouldn't let me edit my last post any more.
ignore the comment that states i see no multiplication i get where your at now. but the rest of my last post has detailed (from my perspective) what is going on in the loop(based upon your code)(i have to ask are you an arithemetic major ?) so basically after rereading your first post mini is reassigned to j so i =mini and (j=mini+1) in your code. so from my point of view this is unsolvable unless your instructor forgot to tell you to initialize k n and integer array a;

another question did you post the entire question?
also here is the revised comments on the code you posted. :)
again moderators super mods and admins sorry for triple it wouldn't let me edit my last post here. :(

[rwill357]

Thank you all for your post. The function I listed above actually came out of my text. I am on a chapter dealing with complexity. I am trying to understand calculating complexity using big-O notation

[rwill357]

Is the following math correct in this case :
(n - 1) + (n - 2) + ... + (n - (k -1)) + (n - k)

[rwill357]

After solving this equation I came up with

2kn – k^2- k/2

so is the big o notation O(k^2)

help

[Anarionist]

After solving this equation I came up with

2kn – k^2- k/2

so is the big o notation O(k^2)

help

2kn=k-k-n-n
k^2=k*k
k/2=k
(math is not my strong subject so i may not have it correctly).
O is aparently want you want returned so my guess is yes
O(k^2)
are you actually going to compile this ? or just speculating?