A Quick Guide to Big-O Notation, Memoization, Tabulation, and Sorting Algorithms by Example
A Quick Guide to Big-O Notation, Memoization, Tabulation, and Sorting Algorithms by Example
Curating Complexity: A Guide to Big-O Notation
- Why is looking at runtime not a reliable method of calculating time complexity?
- Not all computers are made equal( some may be stronger and therefore boost our runtime speed )
- How many background processes ran concurrently with our program that was being tested?
- We also need to ask if our code remains performant if we increase the size of the input.
-
The real question we need to answering is:
How does our performance scale?
.
big ‘O’ notation
- Big O Notation is a tool for describing the efficiency of algorithms with respect to the size of the input arguments.
- Since we use mathematical functions in Big-O, there are a few big picture ideas that we’ll want to keep in mind:
- The function should be defined by the size of the input.

- Big O is simplified to show only its most dominant mathematical term.
Simplifying Math Terms
- We can use the following rules to simplify the our Big O functions:
-
Simplify Products
: If the function is a product of many terms, we drop the terms that don't depend on n. -
Simplify Sums
: If the function is a sum of many terms, we drop the non-dominant terms. -
n
: size of the input -
T(f)
: unsimplified math function -
O(f)
: simplified math function.
Putting it all together
- First we apply the product rule to drop all constants.
- Then we apply the sum rule to select the single most dominant term.
Complexity Classes
Common Complexity Classes
There are 7 major classes in Time Complexity
O(1) Constant
The algorithm takes roughly the same number of steps for any input size.
O(log(n)) Logarithmic
In most cases our hidden base of Logarithmic time is 2, log complexity algorithm’s will typically display ‘halving’ the size of the input (like binary search!)
O(n) Linear
Linear algorithm’s will access each item of the input “once”.
O(nlog(n)) Log Linear Time
Combination of linear and logarithmic behavior, we will see features from both classes.
Algorithm’s that are log-linear will use both recursion AND iteration.
O(nc) Polynomial
C is a fixed constant.
O(c^n) Exponential
C is now the number of recursive calls made in each stack frame.
Algorithm’s with exponential time are VERY SLOW.
Memoization
- Memoization : a design pattern used to reduce the overall number of calculations that can occur in algorithms that use recursive strategies to solve.
- MZ stores the results of the sub-problems in some other data structure, so that we can avoid duplicate calculations and only ‘solve’ each problem once.
- Two features that comprise memoization:
- FUNCTION MUST BE RECURSIVE.
- Our additional Data Structure is usually an object (we refer to it as our memo… or sometimes cache!)
Memoizing Factorial
Our memo object is mapping out our arguments of factorial to it’s return value.
- Keep in mind we didn’t improve the speed of our algorithm.
Memoizing Fibonacci
- Our time complexity for Fibonacci goes from O(2^n) to O(n) after applying memoization.
The Memoization Formula
Rules:
- Write the unoptimized brute force recursion (make sure it works);
- Add memo object as an additional argument .
- Add a base case condition that returns the stored value if the function’s argument is in the memo.
- Before returning the result of the recursive case, store it in the memo as a value and make the function’s argument it’s key.
Things to remember
- When solving DP problems with Memoization, it is helpful to draw out the visual tree first.
- When you notice duplicate sub-tree’s that means we can memoize.
Tabulation
Tabulation Strategy
Use When:
- The function is iterative and not recursive.
- The accompanying DS is usually an array.
Steps for tabulation
- Create a table array based off the size of the input.
- Initialize some values in the table to ‘answer’ the trivially small subproblem.
- Iterate through the array and fill in the remaining entries.
- Your final answer is usually the last entry in the table.
Memo and Tab Demo with Fibonacci
Normal Recursive Fibonacci
function fibonacci(n) {
if (n <= 2) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Memoization Fibonacci 1
Memoization Fibonacci 2
Tabulated Fibonacci
Example of Linear Search
- Worst Case Scenario: The term does not even exist in the array.
- Meaning: If it doesn’t exist then our for loop would run until the end therefore making our time complexity O(n).
Sorting Algorithms
Bubble Sort
Time Complexity
: Quadratic O(n^2)
- The inner for-loop contributes to O(n), however in a worst case scenario the while loop will need to run n times before bringing all n elements to their final resting spot.
Space Complexity
: O(1)
- Bubble Sort will always use the same amount of memory regardless of n.
- The first major sorting algorithm one learns in introductory programming courses.
- Gives an intro on how to convert unsorted data into sorted data.
It’s almost never used in production code because:
- It’s not efficient
- It’s not commonly used
- There is stigma attached to it
-
Bubbling Up
: Term that infers that an item is in motion, moving in some direction, and has some final resting destination. - Bubble sort, sorts an array of integers by bubbling the largest integer to the top.
- Worst Case & Best Case are always the same because it makes nested loops.
- Double for loops are polynomial time complexity or more specifically in this case Quadratic (Big O) of: O(n²)
Selection Sort
Time Complexity
: Quadratic O(n^2)
- Our outer loop will contribute O(n) while the inner loop will contribute O(n / 2) on average. Because our loops are nested we will get O(n²);
Space Complexity
: O(1)
- Selection Sort will always use the same amount of memory regardless of n.
- Selection sort organizes the smallest elements to the start of the array.
Summary of how Selection Sort should work:
- Set MIN to location 0
- Search the minimum element in the list.
- Swap with value at location Min
- Increment Min to point to next element.
- Repeat until list is sorted.
Insertion Sort
Time Complexity
: Quadratic O(n^2)
- Our outer loop will contribute O(n) while the inner loop will contribute O(n / 2) on average. Because our loops are nested we will get O(n²);
Space Complexity
: O(n)
- Because we are creating a subArray for each element in the original input, our Space Comlexity becomes linear.
Merge Sort
Time Complexity
: Log Linear O(nlog(n))
-
Since our array gets split in half every single time we
contribute O(log(n)). The while loop contained in our helper
merge function contributes O(n) therefore our time complexity
is O(nlog(n));
Space Complexity
: O(n) - We are linear O(n) time because we are creating subArrays.
Example of Merge Sort
- Merge sort is O(nlog(n)) time.
- We need a function for merging and a function for sorting.
Steps:
- If there is only one element in the list, it is already sorted; return the array.
- Otherwise, divide the list recursively into two halves until it can no longer be divided.
- Merge the smallest lists into new list in a sorted order.
Quick Sort
Time Complexity
: Quadratic O(n^2)
- Even though the average time complexity O(nLog(n)), the worst case scenario is always quadratic.
Space Complexity
: O(n)
- Our space complexity is linear O(n) because of the partition arrays we create.
- QS is another Divide and Conquer strategy.
- Some key ideas to keep in mind:
- It is easy to sort elements of an array relative to a particular target value.
- An array of 0 or 1 elements is already trivially sorted.
Binary Search
Time Complexity
: Log Time O(log(n))
Space Complexity
: O(1)
Recursive Solution
Min Max Solution
- Must be conducted on a sorted array.
- Binary search is logarithmic time, not exponential b/c n is cut down by two, not growing.
- Binary Search is part of Divide and Conquer.
Insertion Sort
- Works by building a larger and larger sorted region at the left-most end of the array.
Steps:
- If it is the first element, and it is already sorted; return 1.
- Pick next element.
- Compare with all elements in the sorted sub list
- Shift all the elements in the sorted sub list that is greater than the value to be sorted.
- Insert the value
- Repeat until list is sorted.
If you found this guide helpful feel free to checkout my GitHub/gists where I host similar content:
Instantly share code, notes, and snippets. Web Developer, Electrical Engineer JavaScript | CSS | Bootstrap | Python |…gist.github.com
Web Developer, Electrical Engineer JavaScript | CSS | Bootstrap | Python | React | Node.js | Express | Sequelize…github.com
Or Checkout my personal Resource Site:
Memoization, Tabulation, and Sorting Algorithms by Example Why is looking at runtime not a reliable method of…bgoonz-blog.netlify.app


[CHAPTER 661B]
REDRESS FOR WRONGFUL CONVICTION AND IMPRISONMENT
Section
661B-1 Statement of claim for compensation
661B-2 Presentation of claim
661B-3 Judgment and award
661B-4 Time limitations
661B-5 Right of appeal
661B-6 Waiver of sovereign immunity
661B-7 Exclusive remedy


LABYRINTH OF PASSION A film review by T. H. E. White Copyright 1994 T. H. E. White
94 mins, 1982
This crazy story (Almodovar's 3rd feature-length movie) revolves around four central characters: Riza Niro (Imanol "Intruder" Arias), who is the son of the Emperor of Tiran, Sadec (a very young Antonio "MAMBO KINGS/PHILADELPHIA" Banderas), the gay Islamic terrorist with an amazing sense of smell, Sexilia (Celia Roth), the stunning singer and nymphomaniac who is afraid of the sunlight, and Queti (Marta Fernandez-Muro), the dry-cleaner's daughter, fan of Sexilia's and whose father (Luis Ciges) rapes her, believing her to be his own estranged wife.
While hiding from the terrorists, Riza joins a punk band, and a rapport develops between himself and Sexilia. Throughout the film, Sexilia works out in flashbacks how she became a nymphomaniac, afraid of the sun, and how Riza discovered homosexuality.
To really enjoy this film it seems almost essential to be a heavy Almodovar fan. Common themes (homosexuality, nymphomania, incest, hard drugs, rock'n'roll, Madrid life) abound, here stronger than ever. It is a hard film to translate adequately into another language because of the slang and humour of the Madrid "pasotas". The script is fast, lively and sparkling; the acting is both over-the-top and natural. The scenes of Madrid are as colourful as ever.
Much of the script seems to be ad-lib, as if a hidden camera were filming everything. One of the best scenes is a photo-shoot with Fabio (Fany McNamara) posing with a drill. The ensuing conversation between Fabio and Riza Niro must be one of the most memorable dialogues in Almodovarian films.
One interesting point concerning the acting is that neither the terrorists nor Riza Niro make any attempt to feign a `foreign' accent, and keep their pasota-ness throughout. This is intentional, and used for effect later on when Eusebio (Angel Alcazar) and his girlfriend (Cristina S. Pascual) comment on this. On the other hand, Helga Line over-acts her role as Princess Toraya, adding to the delightful naivete of the admirable casting.
One of the jewels of the film is the evocative punk soundtrack. In a club, Pedro Almodovar himself gets up on stage when the announced band, "ELLOS", are late arriving. He and Fabio (his then real-life gay lover) sing a superbly kitch punk rock song, "Suck It To Me", written by Almodovar himself. Later on, when the transformed Riza Niro sings "Gran Ganga", having been asked to sing because the original singer, Eusebio, has broken his leg after Sexilia had made him slip down the stairs on a banana skin, the crowd go wild with admiration. Both "Gran Ganga" (another song from the Almodovar-McNamara discography) and "Suck It To Me" have become timeless classics in Spain among the punk-rock followers.
LABYRINTH OF PASSION is not a family film, but one for an open-minded Almodovar follower. There are many adult themes, though nothing is depicted explicitly. It is indeed a film to watch a hundred times and never tire of. 10 out of 10.
BY: Tristan H E White. | (mail to: T.H.E.White@qmw.ac.uk).
.
The review above was posted to the
rec.arts.movies.reviews newsgroup (de.rec.film.kritiken for German reviews).
The Internet Movie Database accepts no responsibility for the contents of the
review and has no editorial control. Unless stated otherwise, the copyright
belongs to the author.
Please direct comments/criticisms of the review to relevant newsgroups.
Broken URLs inthe reviews are the responsibility of the author.
The formatting of the review is likely to differ from the original due
to ASCII to HTML conversion.
Related links: index of all rec.arts.movies.reviews reviews


Material Design
{% include "partials/navbar.template.html" %}
load > breadcumbs
{% block body%}{% endblock %}


What is TeamCity? It’s a software that you would use to do continuous integration. Continuous integration is very important and it should never be an option on a serious project (that’s is my opinion and I strongly believe in the values it provide).
If you have followed the Building A New Application Series, you may be wondering why I would want to do that after setting up a complete integration server with CruiseControl.NET. Well, I was skeptical when I first heard about all the fuss surrounding this JetBrains project. After all, CruiseControl.NET was doing everything I wanted and more.
So the reason I made the switch is because of the time it take to set it up : 20 minutes. Everything was fully functional in under 20 minutes. I absolutely got no error at all. I just got through all the step of the wizard and then : done. Unit testing, code coverage, build, reports, etc… And it’s absolutely free for small team.
The big downside for me was the lack of support out of the box for other unit testing framework (other than NUnit and MSTest). My project is using MbUnit so I will need to do some more research to integrate it in my build process. But it is possible if you want to invest time in doing so.
So let’s get started with this little tutorial :
1. Download TeamCity.
2. Start the installation.
Just follow all the steps. I encountered a slight problem due to something already on port 80, so I used the port 8080.
I left everything intact in this screen, but this is where you specify some default folder used bu the build agents. The tempDir and workDir will be used to store your application artifacts and even your source file before the compilation if you don’t give it one in the configuration (later).
That’s it, you have installed TeamCity. Now let’s add our project to it.
3. Open TeamCity !!!
Nothing too complicated here, just enter the username/password you want for the administrator account. The email will be used to sent important information the build server would want you to know..
What I like is that you will be taken by the hannd for the rest of the steps. Click on the Create Project link.
Name of the project and a description. It will be useful if several projects are on the same build server.
Now click the Create build configuration link. You can have multiple build configuration by project.
In the build configuration window, you can change the way the build number are generated and the default behavior when the build fail. You can also specify that you want to start with a clean project.
There, you can decide how you want the project to be retrieved from the source control repository and where to put him. You can also decide when to label your build. If you do not want a label on a failed build, you can do so. Next, click on Choose build runner.
TeamCity is not only for .NET project. Several build runner are included such as MSBuild, NAnt, sln2003, sln2005, sln2008, Ant, Maven2, etc… Because I am using MbUnit as a testing framework I have decided to stick with MSBuild. But if you are using NUnit or MSTest you may want to use sln2003, sln2005, sln2008 as they can run your unit tests and tell the coverage of your assemblies. You need to fill in the Solution File Path field with the name of your .sln, it’s relative to your project structure (if it’s in the root, enter only the name of your solution file. Fill the rest of the field if you are using NUnit or MSTest.
Last step! Go to the Version Control Settings tab and click Create and attach new VCS root. Give it a name and choose the version control system (VCS) you want to use. Fill in the required field.
Save, and you’re done!
This is the most basic setup you can have. Of course, there is a lot of other things to configure to your specific needs. You can even have integration inside Visual Studio or Eclipse. As I said before the only downside I found is the lack of support for MbUnit, but I will work something to bypass that.
I may do another post going more in depth if I have time. Or maybe a screencast, that would be a lot of fun. If you’re interested, just leave a comment and I will consider it.


Gay And Bisexual Blood Donation Around The World
by UNILADImagine you and your friend are walking into a blood clinic to donate. You’re given forms to fill out. At the sexual history bit; you both put the same thing – you’re kind of at the same stage of life as each other. When it comes to donating, you are walked through to give blood. Your friend isn’t.
In the UK, we need 1.4 million units of blood every year. Every country will have differing amounts they require, of all different specific blood types. As it stands, this isn’t possible if groups of people are discriminated against when it comes to giving blood.
What this looks like is different for each country. If there isn’t an outright ban, there is a ‘deferral period’ – an amount of time during which a gay or bisexual man must abstain from sex before he is allowed to donate (Ireland has a 12-month deferral, for example). This means many countries are missing out on potentially huge quantities of safe and varied blood types.
It’s not as if we don’t need it. We really do.
Ethan Spibey, who launched Freedom to Donate, a campaign to modernise blood donation laws, said:
The fact is, the pool of donors is decreasing and we urgently need to secure the future of the blood supply.
This is a universal fact, whether it be in the UK, Ireland or beyond.
But there are two things to discuss here.
Firstly, the pool of donors is decreasing but due to the fact hospitals over the past 20 years use less blood thanks to modern procedures like key hole surgery and so need less blood. That doesn’t mean NHSBT doesn’t still need blood, and so their campaigns are to replace as many of the donors who stop donating or because they’re in need of rarer blood types.
Secondly, the fact the law is discriminatory.
Take the UK: according to the EU blood directive, deferral periods (in which the donor abstains from sex before donating) ‘should be appropriate to the risk posed by [a person’s] behaviour’. But, it is left to separate countries to decide the exact rules – and those guidelines are based on sexual orientation, rather than the risks posed by the individual. Plainly, there are thousands of willing and able donors who can safely make the life-saving gesture of giving blood who aren’t allowed to, because they happen to be gay or bisexual men.
Ethan continued:
Rather than broad categories, we need to start using a system of individual risk-assessment.
It’s not just about equality, it’s about donating blood and saving lives.
The restrictions we see today are hangovers from the total bans put in place during the HIV epidemic in the 1980s – but despite the huge advances in blood screening (the residual risk of blood supply being contaminated with HIV is less than one in seven million in the UK and one in 1.47million in the US), gay and bisexual men are still treated differently to straight people.
Various countries have reduced the length of their deferral periods over the years and there has been no evidence to suggest changing this has increased the transmission of blood-borne viruses.
But isn’t the ultimate goal a law that doesn’t discriminate at all? Isn’t it one in which everyone who wants to do the amazing thing of giving blood is treated equally and assessed on their individual behaviour, not their sexual orientation?
Here’s the state of the movement in…
Ireland
A 23-year-old student changed the law in Ireland. After Tomás Heneghan mounted a high court challenge, the outright ban introduced in the 1980s was replaced by a 12-month deferral policy in January 2017. He has now called on Ireland’s Health Minister to replace the 12-month deferral with a three-month deferral or no deferral at all, for all donors. According to Ethan, the environment is ‘ripe’ for change.
France
France had a 12-month deferral period but this year the Ministry of Health announced this would be reduced to four months, effective from February 2020. It said the change marked a ‘first step’ in its plans to bring donor conditions for gay and bisexual men in line with those for heterosexuals by 2022.

United States
In 2015, the country moved from a straight ban to a 12-month deferral, in place at the majority of US blood centres by 2017. More positively, it has promised to reconsider its policies ‘as new data becomes available’, including moving to alternate deferral options, such as the use of individual risk assessment.
In highly conservative and/or religious countries the situation is clearer. There are no bans or deferral periods on gay or bisexual men donating blood in Russia, for example, because homosexuality is not openly recognised. So while there are no donation bans, in terms of equality, countries like this have a lot further to go.
In the UK, Ethan remains positive, saying:
There really is a will to change the rules.
We’ve never been closer to having a policy for gay and bisexual men based in fact and reality, not supposition.
It’s a really exciting time.
While we have people like Ethan fighting for positive change, we’re sure it’ll get done sooner rather than later.


Keynote Speaker
We are very honoured and pleased Dr. Andrew Asher has accepted to give keynotes at ILS-DRF 2021!
Topic: Questions of Value: Libraries, Learning Analytics, and Student Privacy
Speaker Bio: Dr. Andrew Asher is the Assessment Librarian at Indiana University Bloomington, where he leads the libraries’ qualitative and quantitative assessment programs, conducts research on the anthropology of information, and teaches research methods in information science. Asher’s most recent work examines search and discovery workflows of students and faculty, information fluency development, and the ethical and privacy dimensions of learning analytics data. He is currently a member of the Data Doubles research team, a three-year IMLS funded study of student perspectives of privacy issues associated with learning analytics initiatives in libraries. Asher holds a PhD in sociocultural anthropology from the University of Illinois at Urbana-Champaign, and has written and presented widely on applying ethnography and mixed-methods research in academic libraries, including the co-edited volume, College Libraries and Student Culture.


{% extends "base.html" %} {% block title %}Manage myTBA - The Blue Alliance{% endblock %} {% block meta_description %}Manage your favorites and subscriptions{% endblock %} {% block content %}
myTBA Team successfully updated.
myTBA Event successfully updated.
myTBA Match successfully updated.
Here you can manage your favorites and subscriptions.
Favorites are used for personalized content and quick access.
Subscriptions are used for push notifications.
| Number | Name | Favorite | Subscriptions | Edit |
|---|---|---|---|---|
| {{team.team_number}} | {{ team.nickname }} | {% if fav %}{% endif %} |
|
You have no teams!
{% endif %}| Event | Favorite | Subscriptions | Edit |
|---|---|---|---|
| {{ event.year }} {{ event.short_name }} [{{ event.event_short.upper() }}] | {% if fav %}{% endif %} |
|
You have no events!
{% endif %}| Match | Favorite | Subscriptions | Edit |
|---|---|---|---|
| {{ match.verbose_name }} | {% if fav %}{% endif %} |
|
You have no matches!
{% endif %}