Hi Stephanie, I'm wondering which courses you were introduced to Python and which book you are using. I do understand how it might be difficult to understand this concept, especially for someone who is a complete novice to algorithm analysis where Big O shows up. I'll answer you inline.
-----Original Message----- From: Tutor [mailto:tutor-bounces+joseph.lee22590=gmail....@python.org] On Behalf Of Quiles, Stephanie Sent: Monday, July 27, 2015 6:30 PM To: python tutor <tutor@python.org> Subject: [Tutor] the big o > Hello, > I am trying to figure this out but i do not understand any of it. the question asks give the big-o performance of the following code fragment: > for i in range(n): > for j in range(n): > k = 2 + 2 > I am not sure how i am supposed to figure this out. i have been reading the book, looking at blog posts and watching online tutorials and i still cannot grasp the > big-o. please keep in mind that i have never taken a calc course and that i am a complete novice to programming, even more so to python. Any help would be greatly appreciated. I am pretty much on my own with these since my fellow students are unwilling to help me with anything since they are far more advanced than i am. > Thank you, > Stephanie JL: Okay, let's start from the very beginning. First, before talking about what Big O means, it is important to go over some basics: Big O comes from algorithm analysis, a branch of computer science dealing with coming up with solutions to problems and analyzing them. In our context, an algorithm is a list of precise steps to solve a problem. For example, using Alan's searching example, it could be paraphrased as follows: Suppose I have a list of items and I want to search for a specific item. How would I do this? If your friend was asked to do this, what would he or she do? Obviously, your friend will search for items one at a time until what you are looking for is found. You or your friend could say: First, have a list of items. Then examine one item at a time until what I want is found. This is a description of an algorithm: precise steps to be followed. The above paragraph describes searching algorithms - given a list of items, a computer (or a machine whether it's physical or virtual) will go through the list and compare each item to the target it is looking for. There are more elegant ways of doing it that mimics how humans perform specific searches, including the one that Alan described (called logarithmic search, commonly introduced as binary search in earlier courses). Once you have an algorithm, it is time to think about how to implement, or write it in Python. This is where you need to become skilled at translating paper instructions to something that Python can understand. In case of Alan's linear search example, one way to put it is: For item in items: if item == target: position = items.index(item) return position Essentially, this code fragment says to perform a linear search on a list of items. As part of learning about Big O and algorithms, it is important to practice how to translate between English and Python: translate a description of an algorithm in English to Python by implementing it, and understand what the code fragment does. Now the topic at hand: For decades, computer scientists and software developers were asking themselves, "how can we make our programs run faster and use fewer resources?" This is where Big O comes into play: Many computer science textbooks define Big O as worst--case running time of algorithms. That is, Big O describes how an algorithm will behave when it encounters input that'll cause it to run slowest. In a nutshell, an algorithm (or a program) will take in a set of values (called input), do something with it (searching, sorting, send and receive data between computers, etc.) and return one or more results (output). Many people would want to assume that algorithms will work on typical data only. In reality, algorithms can encounter input that it may have hard time to process. For example, if a program is asked to sort a list, it will expect to get a list of items that can be sorted using fewest resources and can be done quickly. There is one kind of input that this program will have hard time with (I'll let you figure out what this input might be; may I ask that we let Stephanie figure this out? That way she can understand how algorithm design works). Now you know what the worst possible input to an algorithm is like, you are ready to tackle the actual definition of Big O. Simply put, Big O is running time of an algorithm given a worst-case input. This is way different from what the book asks: the question and the accompanying code fragment simply asks for running time, not exactly Big O, hence the reason I asked which course you are taking and book that's used (Big O is reserved for computer science courses dealing with algorithms). Based on our discussion so far, there must be one more thing involved when talking about Big O: input data, and I'm leaning towards shaking my head at this point, seeing that the question could confuse novices (it is way too early to be introduced to Big O unless if you are taking a course in algorithms). In case of the code fragment above, as I said in a previous message, the easiest way to calculate Big O is to look at what the inner loop does. Once you understand that, look at the outer loop. I think the easiest way to look at this is through a real-life example: suppose you have a bunch of boxes full of books, and you want to find a specific book. You would open each box and look through various books, looking for the book you need. If you didn't find the book you are looking for, you'd move onto the next box, right? That's exactly what's going on here: * The inner loop: you look for books in one box. * Outer loop: you repeat this search for all boxes. And the result you get is the running time of this algorithm. It turns out there are more elegant ways to do this given the right input, and this algorithm or a variation is invoked in many real-life situations such as searching for a character in strings, searching for files in folders, sorting and so on (hint: the running time of this algorithm is not logarithmic; there are logarithmic (chopping) algorithms that has polynomial Big O value, with a well-known example being quicksort (you tell the algorithm to define a pivot that'll be used to align items for ease of sorting) which has Big O or worst-case running time of N squared). Hope this helps. Good luck in your courses. Cheers, Joseph _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
