Find the running time in Big O notation

1)  for (i = 1; i < n; i++) {                         > n
2)      SmallPos = i;                                 > n-1
3)      Smallest = Array[SmallPos];                   > n-1
4)      for (j = i+1; j <= n; j++)                    >  n*(n+1 -i-1)??
5)          if (Array[j] < Smallest) {                > n*(n+1 -i-1 +1)  ?? 
6)              SmallPos = j;                         > n*(n+1 -i-1 +1)  ?? 
7)              Smallest  = Array[SmallPos]           > n*(n+1 -i-1 +1)  ??     
            }                                         
8)      Array[S开发者_C百科mallPos] = Array[i];                   > n-1
   9)                Array[i] = Smallest;             > n-1
                                     }

i know the big O notation is n^2 ( my bad its not n^3)

i am not sure between line 4-7 anyone care to help out? im not sure how to get the out put for the second loop since j = i +1 as i changes so does j

also for line 4 the ans suppose to be n(n+1)/2 -1 i want to know why as i can never get that

i am not really solving for the big O i am trying to do the steps that gets to big O as constant and variables are excuded in big O notations.

---

I would say this is O(n^2) (although as Fred points out above, O(n^2) is a subset of O(n^3), so it's not wrong to say that it's O(n^3)).

Note that it's generally not necessary to compute the number of executions of every single line; as Big-O notation discards low-order terms, it's sufficient to focus only on the most-executed section (which will typically be inside the innermost loop).

So in your case, none of the loops are affected by the values in Array, so we can safely ignore all that. The innermost loop runs (n-1) + (n-2) + (n-3) + ... times; this is an arithmetic series, and so has a term in n^2.

---

Is this an algorithm given to you, or one you wrote?

I think your loop indexes are wrong.

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

should be either

for (i = 0; i < n; i++) {     

or

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

depending on whether your array indexes start at 0 or 1 (it's 0 in C and Java).

Assuming we correct it to:

for (i = 0; i < n; i++) {
    SmallPos = i;
    Smallest = Array[SmallPos];
    for (j = i+1; j < n; j++)
        if (Array[j] < Smallest) {
            SmallPos = j;
            Smallest  = Array[SmallPos];
        }                                         
    Array[SmallPos] = Array[i];
    Array[i] = Smallest;
}

Then I think the complexity is n²-3/2n = O(n²).

Here's how...

The most costly operation in the innermost loop (my lecturer called this the "basic operation") is key comparison at line 5. It is done once per loop.

So now, you create a summation:

Sum(i=0 to n-1) of Sum(j=i+1 to n-1) of 1.

Now expand the innermost (rightmost) Sum to get:

Sum(i=0 to n-1) of (n-1)-(i+1)+1

and then:

Sum(i=0 to n-1) of n-i-1

and then:

[Sum(i=0 to n-1) of n] - [Sum(i=0 to n-1) of i] - [Sum (i=0 to n-1) of 1]

and then:

n[Sum(i=0 to n-1) of 1] - [(n-1)(n)/2] - [(n-1)-0+1]

and then:

n[(n-1)-0+1] - [(n^2-n)/2] - [n]

and then:

n^2 - [(n^2/2) - n/2] - n

equals:

1/2n^2 - 1/2n

is in:

O(n^2)

---

If you're asking why it's not O(n³)...

Consider the worst case. if (Array[j] < Smallest) will be true the most times if Array is reverse sorted.

Then you have an inner loop that looks like this:

    Array[j] < Smallest;
    SmallPos = j;
    Smallest  = Array[SmallPos];

Now we've got a constant three operations for every inner for (j...) loop.

And O(3) = O(1).

So really, it's i and j that determine how much work we do. Nothing in the inner if loop changes anything.

You can think of it as you should only count while and for loops.

---

As to why for (j = i+1; j <= n; j++) is n(n+1)/2. It's called an arithmetic series.

You're doing n-1 passes of the for (j...) loop when i==0, n-2 passes when i==1, n-3, etc, until 0.

So the summation is

n-1 + n-2 + n-3 + ... 3 + 2 + 1

now, you sum pairs from outside in, re-writing it as:

n-1+1 + n-2+2 + n-3+3 + ...

equals:

n + n + n + ...

and there are n/2 of these pairs, so you have:

n*(n/2)

---

Two for() loops, the outer loop from 1 to n, the inner loop runs between 1..n, to n. This makes it O(n^2).

If you 'draw this out', it'll be triangular, rather than rectangular, so O(n^2), while true, is hiding the fact that the constant factor term is smaller than if the inner loop also iterated from 1 to n.

---

It is O(n^2).

For each of the n iterations of the outer loop you have n iterations in the inner loop.