×
Log in to StudySoup
Get Full Access to NYU - ENGR 2134 - Study Guide
Join StudySoup for FREE
Get Full Access to NYU - ENGR 2134 - Study Guide

Already have an account? Login here
×
Reset your password

NYU / Mechanical Engineering / ENGR 2134 / What is the meaning of big-oh?

What is the meaning of big-oh?

What is the meaning of big-oh?

Description

School: New York University
Department: Mechanical Engineering
Course: Data Structures & Algorithms
Professor: Linda sellie
Term: Fall 2016
Tags:
Cost: 50
Name: Study Guide for Data Structures and Algorithms
Description: Covers all the Test Topics: 1. Determine the big-Oh run time for a code snippet 2. Estimate the run time an algorithm will take on an input of size n, given the run time of the algorithm on an input of
Uploaded: 09/27/2016
4 Pages 39 Views 1 Unlocks
Reviews


Shlomi Oved Study Guide for Midterm 09/26/16


What is the meaning of big-oh?



Topics on Midterm:  

• Determine the big-Oh run time for a code snippet

Intro to Big-Oh

• Consider running time vs input size

• We’re interested in general behavior not exact details

o Ignore lower order terms

o Ignore multiplicative constant

• Example: n(n+1)/2 is O(n2)

• Graph has “same shape”

Formal definition

T(n) is O(g(n)) is there are positive c and n0 such that T(n)<=cg(n) when n>=n0 3n is O(n) We also discuss several other topics like When is the wall street bombing?

3n+ 10n2 is O(n2)


What is the big-oh notation?



If you want to learn more check out What is the largest immigrant group in the united states today?

Big-Oh notation

• C g(n) is an upper bound growth rate, for some constant c

• Platform-independent (not affected by choice of computer, compiler,  operating system, etc.

• G(n) is written as simply as possible where constants an low order term are  omitted

Some Important Big-Oh’s

• O(1)- constant

• O(log n)- logarithmic

• O(n)- linear

• O(n log n)- linearithmic

• O(n2)- quadratic

• O(n3)- cubic

• O(2n)- exponential

• O(n!)- factorial


What are some important big-oh’s?



Big Theta is more precise than Big-Oh

Examples of Running Times

• Find element k of array A: O(1)

• Find kth element in a list: O(n)

• Find smallest element in array: O(n)

• Find smallest element in sorted array: O(1)

• Insertion sort: O(n2) We also discuss several other topics like What is andare a cavallo in english?

• Merge sort: O(n log n)

• Use a vector class iterator

• Vector class has a Random Access Iterator.

Shlomi Oved Study Guide for Midterm 09/26/16

• The Random class Iterator can do the following actions:

• Itr1< itr2, itr1 <= itr2, itr-=c, itr +=c, itr2-itr1, itr1+c, itr1-c, itr[c], itr1>=itr2,  itr1>itr2, --itr, itr--, Itr++, ++itr, *itr, itr1==itr2, itr1 != itr2, itr->m • Example of a function using Vector iterator:

• template<class Object, class Iterator>

• void goThroughVector(const vector<Object>& objects){

• for(Iterator itr=objects.begin(); itr!=objects.end(); itr++){

• cout << *itr << endl;

•      }

• }

• Write a functor

• Example of functors:

• class isEven{

• public:

•          bool operator()(const int& evenNumber){return evenNumber%2==0;} • };

• template<class Object, class Functor> If you want to learn more check out What is the meaning of abnormal psychology?

•          bool evenOrOdd(const Object& obj, Functor funct){

•         return funct(obj);

• }

• class strCompare{

• public:

•          bool operator()(const string& str1, const string& str2){return str1<str2;} • };

• template<class Object, class Functor>

•         bool isShorter(Object obj1, Object obj2, Functor funct){

•         return funct(obj1, obj2);

• }

• Write a generic function template for some algorithm where the  parameters to the function are iterators and functors

• Ex:

• template <class Itr, class UnaryPred> We also discuss several other topics like What is the absolute constant error?
We also discuss several other topics like What is the content of bergmann’s rule?

• void print_if(Itr start, Itr end, UnaryPred pred){

•            for (Itr itr=start; itr!=end; itr++){

•                 bool result=pred(*itr);

•                if (result) cout << *itr << endl;

•         }

• }

• Know how iterators work for the vector and list class

• For the list class iterators are forward directional iterators or bi-directional  iterators depending on the type of list.

Shlomi Oved Study Guide for Midterm 09/26/16

• Possible Operations of Iterators

• Forward Iterators:

• Itr++, ++itr, *itr, itr1==itr2, itr1 != itr2, itr->m

• Bi-Directional iterators:

• --itr, itr--, Itr++, ++itr, *itr, itr1==itr2, itr1 != itr2, itr->m

• Vector class has a Random Access Iterator.

• The Random class Iterator can do the following actions:

• Itr1< itr2, itr1 <= itr2, itr-=c, itr +=c, itr2-itr1, itr1+c, itr1-c, itr[c], itr1>=itr2,  itr1>itr2, --itr, itr--, Itr++, ++itr, *itr, itr1==itr2, itr1 != itr2, itr->m

• Write a copy constructor, move constructor, move assignment operator,  copy assignment operator, or destructor for a class

• Example:

• //Copy Constructor  IntArray::IntArray(const IntArray& rhs) {  •               size = rhs.size;

•               array = new int[size];

• for (int i = 0; i < size; i++) {  

• array[i] = rhs.array[i];  

•            }

• }

• //Move Constructor

• IntArray::IntArray(IntArray&& rhs) {

• size = rhs.size;

• array = rhs.array;  

•              rhs.array = nullptr;  

•              rhs.size = 0;  

• }  

• //Copy Assignment Operator

• IntArray& IntArray::operator=(const IntArray& rhs) {

• //self check

•    //copy over  

•               if (this != &rhs) {

•        size = rhs.size;

•                     array = new int[size];

•                     for (int i = 0; i < size; i++) {

• array[i] = rhs.array[i];  

• }  

•                   }  

•                     //return  

•                    return *this;  

• }  

• //Move Assignment Operator

• IntArray& IntArray::operator=(IntArray&& rhs) {

Shlomi Oved Study Guide for Midterm 09/26/16

• if (this != &rhs) {

• size = rhs.size;

• delete[] array;  

• array = rhs.array;

• rhs.size = 0;

• rhs.array = nullptr;

• }  

•                   return *this;  

• }  

• //Destructor

• IntArray:: ~IntArray(){  

•              size = 0;

•             delete[] array;  

• }

Page Expired
5off
It looks like your free minutes have expired! Lucky for you we have all the content you need, just sign up here