×
Join StudySoup

×

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

# What is the meaning of big-oh? Description

##### 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
4 Pages 128 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)

3n+ 10n2 is O(n2)

## What is the big-oh notation?

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(n3)- cubic We also discuss several other topics like Who is robert “fighting bob” la follete?

• 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)

• 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: If you want to learn more check out How did immigrants assimilate to and change american culture?

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

•          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); We also discuss several other topics like What is andare al cinema in english?

• }

• 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 How is treatment defined?

• 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;

•         } If you want to learn more check out What is the absolute constant error?

• }

• 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 If you want to learn more check out What is the content of bergmann’s rule?

• 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
It looks like your free minutes have expired! Lucky for you we have all the content you need, just sign up here
References: