If anyone can help with this college "Order of Magnitude"
problem I would greatly appreciate it. Our professor gave us this problem for homework and we are all stumped. The entire class doesn't understand what is being asked and what has to be written down. Online help is scarce with this. This is a CIS 150 "Topics in Computing" class. Frankly, we don't know where to start. We understand the general knowledge of a selection sort, bubble sort, etc.

THE PROBLEM:

int arr[100][100]

while (i < 100)
if (i mod 2 == 0)
SelSort(arr[][], i)

Assume that sel sort is a method that performs a selection sort on a one dimensional array of 100 integers.

Perform an order of magnitude analysis on the code above.
First give the unreduced order of magnitude, then apply the rules of Big O notation in a step by step (show each clearly) approach to reduce to its final form.

Show work below:

FINAL= _____O( )_____

is that supposed to be SelSort( arr[i][], i );?

The wikipedia page for selection sort already has some analysis: http://en.wikipedia.org/wiki/Selection_sort

Hi,

I think this has to do with algorithm analysis & Big O notation, so maybe the title is a bit unfortunate.

Search on wiki for Big O notation.

Some basic ideas, with examples:

O(1) : return the i'th value (known) in an array or similar container that has subscript MyContainer[i] . This is done by subtracting pointers, so is very direct.

O(n) : search through a container as above for a value , but the subscript isn't known - so each item in the container must compared - worst case is n the number of elements in the container. Average case is n/2

O(log n) : Search in a binary sort tree (BST). It is log n because each time a node is traversed, it represents a halving of the remaining data to search.

There are other very inefficient examples, such as n², n³, exponential etc.

When I was at uni 20 years ago, we had an entire textbook about this.

To start you all off, first there is while (i < 100), so that is O(n). But then there is if (i mod 2 == 0), so now it is O(n/2).

It is important to establish variables for the size of the array - even though it is 100 by 100. In O(n/2) above n is the number of rows in the array, but the sort function operates on all 100 columns, so I think it is important not to get confused by this, so create a variable for the number of columns.

Hope all is well :+)

Edit:

Not relevant to the problem, but helpful nonetheless.

I always uses braces, even when the is 1 statement, so I would write that code like this:



And I dislike using variable like i and j or m and n and others, because their similarity can cause readability issues and lead to errors. Especially for 2 dimensional Containers.

Years ago I was helping someone who had 2 pages of code full of i and j subscripts. The code compiled, but had a nasty runtime error. So I suggested changing i to Row and j to Column. The error became fairly obvious, because there was a Row, Row, which it should have been Row, Column

This would have still taken some time to fix even with a debugger - it only segfaulted sometimes when Row > Column (subscript out of bounds), so I guess it was a really good lesson on how good coding practices can make one life much easier.

Thanks for the help and explanation. I'm still confused about what he is asking. He's asking for an "order of magnitude analysis" and a "step by step" reduction to it's final form. Is that the part that goes from O(n) to the final answer? Or do we have to draw out an entire 100x100 array with numbers in it? or do we just follow the while loop through? counting how many times each action will be performed? Sorry to have so many questions about this, but we weren't even issued a "book" for this course. It's all from the lectures and I'm not a programmer.

So what you are trying to do is figure out the efficiency of the program.

To do this go through the code and look for things like loops that effect the efficiency or complexity. For example, to search for a value in a 2 dimensional array, we need a nested for loop - the outer one for the rows, and a nested one for the columns. If the array has A rows and B columns then we have (O)A * B , because it has to do A * B comparisons. If it the array is square (n by n) then we have (O) n² or (O) A²


I found this when I Googled wiki big O notation

http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Look at the code here:

http://en.wikipedia.org/wiki/Selection_sort

Can you tell me why it is (O)n² ? It's similar to the scenario above.

When analysing the code, we are not so much interested in the body of loops or functions - more so in how many times loops iterate, and the multiplicative effect of nesting loops, or on the other hand things that reduce the complexity like if (i mod 2 == 0)

This is important, because the choice of algorithm can make a big difference - it helps if you imagine the code is going to be run on a large data set - millions or billions of items. A good algorithm might execute in less than 1 second, a bad one might take 1000 years !!

I had a problem that involved factorials up to 20! Rather than nest extra for loops into already nested loops to calc the factorial, I cheated & worked them all out and put them into an array. This improved the run time from 45 seconds to 1 second.

:+)