Computational Complexity/Sorts/Search

[EurasianVixen]

Does anyone know if this stuff will be on the exam?  Cuz my prof never covered it in class.
Also, which sorts/searches will most likely be on the exam?  I heard it was only binary search (the one from tutorial)...
but what about the rest?
Thanks  

[Evotamer]

Best Search to know is the Binary one if the list is already sorted and if it's something you can use the compareTo() thing or just a '<' modifyier. ...

Sorting best is probably quick sort but that's something you learn later... Right now try to know Bubble sort.
Umm the way the thing works is that you have an item at the i'th position in the array.. then you compare it with i+1, i+2 ....  (Size - 1). If something is greater than the thing you're comparing swap the two...

Hmm maybe that didn't explaination didn't work well let's try some pseudo code

for (i = 0; i < sizeOfArray; i++) {
   for (j = i + 1; j < sizeOfArray; j++) {
        if (array < array[j] ) {     // assuming it's an int
           object temp = array;   //or whatever you're using
           array = array[j];
           array[j] = array;
        }
    }
}
This runs in umm O(n^2).  So it runs slower than something like Quick Sort but Quick Sort got a lot more coding . Ummm I think that thing up top works... but there might be some small 'bug's since it's 4am in the morning and I'm a bit umm dead in the head.

[EurasianVixen]

Thanks.  But what about complexity? Anyone know if that will be on the exam?  

[Yingster]

theres not much to say about complexity, is there?

[Evotamer]

Time Complexity mainly shows how 'complicated' your program is.

For the example below the complexity is n^2. Since the first loop runs at most n times and the second loop also runs n times. Also since the second loop is nested in the first, then you have a multiplier effect.

I don't think you need to know much about complexity in 108, since you learn it in full detail in 148. But it mainly means how complicated your loops and such are.

[Brutal_Chicken]

Well, if they do ask about an algorithm's complexity just remember that the sorts shown were all of Order (n²). They didn't show mergesort right? And Binary search is O (log₂n) and Linear search is O (n). We weren't shown how to derive these time complexities other than 'intuitively' so no worries there.