[Tutor] the big o

[Quiles, Stephanie]

Hi Jason, 

I took Intro to Programming at Albright College and we used Starting Out with Python 3rd ed. Right now I am taking Data Structure and Analysis and we are using This book : http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html 

Thanks Alan for your explanation. The problem with me getting these terms and things is in part due to the accelerated rate in which my classes run. I cant possible master anything in a 6-8 week course, especially when I have zero programming background and about 2/3 of the class does... So I'll fake it till I make it. 

Thanks a lot. I think I have a very basic understanding of Big O right now. But if someone could please make it a little easier to figure out postfix and infix? My homework assignment asks me to convert from infix to postfix. I got a very very basic understanding of this but when the problems get a little more involved I get totally lost. Here is an example A+B/C*D-E+F 

I thought it was something like ABC/+ cd*ef+-?? 

That's probably wrong but I am trying 

Stephanie Quiles
Sent from my iPhone

> On Jul 28, 2015, at 10:07 AM, Joseph Lee <joseph.lee22590 at gmail.com> wrote:
> 
> 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.com at python.org] On
> Behalf Of Quiles, Stephanie
> Sent: Monday, July 27, 2015 6:30 PM
> To: python tutor <tutor at 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 at python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor
>