[Tutor] the big o

[Quiles, Stephanie]

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
_______________________________________________
Tutor maillist - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[Alan Gauld]

On 28/07/15 02:30, Quiles, Stephanie wrote:
> 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 still cannot grasp the big-o.


The big O is a way of describing the relative performance
of an algorithm. For example if you have a random list
of N values and want to find a particular one you need to
search the list looking at each item until you find the one
you want. That could mean doing anything from 1-N lookups.
But on average it would be N/2 (Do you understand how I
got that value?) So the big-O performance of our search
is O(N/2) The result will, on average take N/2 operations.

Now if the list were sorted into ascending order we can
speed that up significantly by using an algorithm called
a binary-chop. That means we start by looking at the middle
item and seeing if it is bigger or smaller than our search
item. If its smaller we can limit the search to the lower
half of the list. We now apply the binary chop again and
once more limit the list to half of the new list. Eventually
we get a list of one item which contains our item(assuming
it existed of course!) It turns out the number of chops we
need is log2(N) (ie for 16 items we need at most 4 chops
to find the item) So the algorithm is O(log2(N)) which is
faster than O(N/2)

Does that make sense so far?

Looking at your example you have a variable 'n' that controls
how many operations you will perform. Can you see how many
times the addition (k = 2+2) will be performed?
is it n?
is it 2*n
is it n*n?
something else?

The answer is your big-O value.

HTH
--
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos


_______________________________________________
Tutor maillist - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[Joseph Lee]

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=***@python.org] On
Behalf Of Quiles, Stephanie
Sent: Monday, July 27, 2015 6:30 PM
To: python 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 - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

_______________________________________________
Tutor maillist - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[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 <***@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=***@python.org] On
> Behalf Of Quiles, Stephanie
> Sent: Monday, July 27, 2015 6:30 PM
> To: python 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 - ***@python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor
>
_______________________________________________
Tutor maillist - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[Alan Gauld]

On 28/07/15 20:08, Quiles, Stephanie wrote:

Hoi Stephanie,

Please start a new topic on a new thread/subject.
It makes funding stuff in the archives much easier.


> ...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. ...
> Here is an example A+B/C*D-E+F
>
> I thought it was something like ABC/+ cd*ef+-??
>

If I work this back correctly it translates as:

(A+B/C) (C*D)-(E+F)

which seems to miss an operation? It also uses C twice.

The first thing you need to do it work out how to put parens
on the original to express the precedence precisely. Then
the postfix format should pretty much drop out.

Do you have access to an RPN calculator(emulator)?
That will help you test it. If on *nix try xcalc -rpn

HTH
--
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos


_______________________________________________
Tutor maillist - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[Danny Yoo]

> 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.


This makes sense. If you can, it might help to look for personal
support at your college too. Of course, we'll be happy to help on
this mailing list! But face-to-face support can also be very helpful,
because email can be parsimonious.

Some colleges have organizations and societies that offer help with
classwork. If such "peer tutoring" services are available on your
campus, I'd strongly recommend connecting with them. For example,
when I went to Berkeley, I used the services of Eta Kappa Nu.
(https://hkn.eecs.berkeley.edu/tutor/) Good folks. And I would
assume that there are similar groups at Albright College.
_______________________________________________
Tutor maillist - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor