#space complexity

[cloudtechlife]

Unique Triplets Problem Situation

Problem Statement

Given an array of unsorted numbers, find all unique triplets in it that add up to zero.

Example 1:

Input: [-3, 0, 1, 2, –1, 1, –2]

Output: [-3, 1, 2], [-2, 0, 2], [-2, 1, 1], [-1, 0, 1]

Explanation: There are four unique triplets whose sum is equal to zero.

  Example 2:

Input: [-5, 2, –1, –2, 3]

Output: [[-5, 2, 3], [-2, –1, 3]]

Explanation: There are two unique triplets whose…

View On WordPress

[joyjing1-blog]

W2D4 - Big-Oh Notation

Topics

Big-Oh Notation

Simplicity: O(2n+4) == O(n)

Dominant Family: O(1) + O(n!) == O(n!)

Treat as families/categories of functions

Deals with worst case scenario / upper bound

O(g) { f | c*f does not dominate g} for some constant c -- belongs in the set of functions

Time Complexity

Space Complexity

Asymptotic Analysis - describe behavior of a function as it approaches infinity

Asymptotic != Amortization

RAM Model of Computation

Assumes we're running our algorithm on a hypothetical Random Access Machine, where data/processing can get infinitely large

Moore's Law - observation/projection that estimates that the number of transistors in a dense integrated circuit doubles approiximately every two years

XOR - Exclusive Or, written as ^ in Ruby. Can do some cool math - [1,2,3] xor-ing 0000 by 1 (0001), 2 (0010), and 3 (0011) would result in identity again

Assessment2 - Took Practice Assessment this morning, 1 hour to work through their RSpecs to write a Blackjack game. Finished with a few minutes to spare, focused on reading/fulfilling RSpecs

Projects

Execution Time Differences/Algorithms

my_min(list) - O(n^2) & O(n) versions

largest_contiguous_subsum(arr) - O(n^2) & O(n) versions

Anagrams

first_anagram?(string1, string2) - O(n!), permutation

second_anagram?(string1, string2) - O(n^2), nested loops

third_anagram?(string1, string2) - O(nlogn), quick-sort 2 arrays

fourth_anagram?(string1, string2) - O(n), 2 hashes

fifth_anagram?(string1, string2) - O(n), 1 hash

Two sum Problem

bad_two_sum?(arr, target_sum) - O(n^2), nested loops

okay_two_sum?(arr, target_sum) - O(nlogn), binary search

great_two_sum?(arr, target_sum) - O(n), 1 hash

Windowed max range

max_windowed_range(array, window_size) - O(n + 2w), expensive to run through window twice to calculate max/min in every window

O(n) time using a MaxMinQueStack

MaxMinQueueStack - create a MyStack class that tracks max & min using @max_array & @min_array. In a new QueueStack class

Initialize - [MyStack1, MyStack2]

Enqueue - Mystack1.push(el)

Dequeue - take all elements from MyStack1, push to MyStack2 (should flip stack, like a slinky) then Mystack2.dequeue. If no elements on MyStack1, then dequeueing will run in O(1) time since know exactly where element is. Amortized time is constant

Max/Min - track within QueueStack, similar way to how we tracked in MyStack

Partner: Sarah Fuchs

Learnings

Algorithms are fun!!!!

Big-Oh Notation is like extremely hand-wavy math that rounds a lot

Merge Sort - runs in O(nlogn) time because each level of the process will require:

T(n) = O(1) + 2T(n/2) + O(n) time per level

log(n) + 1 distinct levels

O(n) * O(logn) = O(nlogn) time complexity

Quick Sort - O(nlogn) average worst case time complexity

Worst case - O(n^2) if always choose the smallest object

Practically, often more efficient to use middle element as pivot rather than first element, in case array has been sorted (correct direction or opposite)

Bubble Sort - worst case scenario is O(n^2)

Binary Search - O(logn), worst case scenario is O(n^2)

[codewardbound]

B-I-G-O BINGO! Nope, just Big-O

Interviewer: "What's the time and space complexity of that solution?" 

Interviewee: "How many stormtroopers does it take to replace a lightbulb?"

Interviewer: "What?"

Interviewee: "Two - one to screw the bulb in, the other to shoot him and take the credit. LOL!"

Interviewer: "What?"

Interviewee: "Well, you said space and you look like a StarWars kinda guy so I figured..."

Interviewer: "Yes? You figured what?"

Interviewee: "Oh...I don't actually have ummm...anything to say after that. I was just hoping to trail off and not be noticed"

Interviewer: "I see. But seriously what's the answer-"

Interviewee: "Who wants cake?!"

Don't let the above situation happen to you. Time and space complexity or Big-O Analysis is actually a really important, valuable skill to have as a developer. The reason interviewers tend to obsess over this is because at scale, any improvements in processing time and/or storage space can greatly affect an application's experience. This can tie directly to the bottom-line (in other words "CHA-CHING!!!")

This is going to come up a lot. So while you're sitting down and throwing your hands in back of your head in admiration of whiteboarding so impressive you're waiting for Ada Lovelace to rise up and come straight to your interview, just to give you a high five, remember you might need to make it better. 

Some interviewers are going to ask you to optimize your solutions using Big-O analysis. It's even better if you can do this on your own without the probing.

So I'll just do a tiny intro here that you can take and hopefully use a foundation to derive more complex analysis from. 

Space...the final frontier

Finding the space complexity is actually not that hard, the name just sounds intimidating. It's literally the amount of additional space you would need for your solution. So if you need to put all the elements from one array of size "n" into another array thats O(n) space. If you define a function with local variables, each of those variables take up constant space or O(1).

Sometimes recursive solutions require more space than iterative ones so just keep that in mind. Make sure to point out these tradeoffs to your interviewer, they like that kinda stuff.

Time...

To find the time complexity of a solution you would, quote unquote, simply count the number of statements/calculations/steps needed to get to your solution, in terms of the size of your data set, usually size of "n".

So if you have a loop, that goes over a the entire length of an array and performs an action to each element, like adding 1, that time would be linear or O(n). If you have some algorithm that takes advantage of halving or doubling the data set it's probably going to be around logarithm time or O(log n). We talked about this in more detail in the Binary Search Tree post.

Now things can get more complicated when you start talking about best, average and worst case scenarios. Very much as the naming implies, they refer to the best, average and worst case times of the solution. The way you would calculate these times are very much based on your implementation of the solution.

The idea of the worst case time is usually derived using amortized analysis, meaning taking into account the rare scenarios that would take the absolute most time - the edge cases. The best case is really theorectical, like if all the sun gods were shining on your algorithm that day and everything went perfectly. The average case is really what you're after, since it's the most realistic case that tries to take into account all the randomness and quirks of real life. 

This is just the tip of the iceberg but these are the building blocks. Understand this stuff and you're golden!

Don't worry if this is all greek to you now. Just absorb and keep it in the back of your head. I didn't know much about this stuff either until the situation at the top happened...in my head! The story above happened in my head. I made it up! It's not from experience. Gosh, my story is much more embarrassing than that.

Hope this helps, whether you're actively interviewing for developer roles, looking to improve your own code or just trying to impress your easily excitable boss that you made it go fast. Check out the resources below. Don't procrastinate unless you want to be a Darth...Waiter! ::rim shot:: I'll be here all week!

Resources:

Beginner's guide to Big-O

Big-O in plain english

Time complexity Wiki

Space complexity

Big O cheat sheet

[fuckyeahterminals]

Classic Nintendo Games are NP-Hard

haha wtf. here is a link to the abstract. Here is the actual article.