UNC-Chapel Hill COMP 550 - symptotic Notation, Review of Functions & Summations (39 pages)

Previewing pages 1, 2, 3, 18, 19, 37, 38, 39 of 39 page document View the full content.
View Full Document

symptotic Notation, Review of Functions & Summations



Previewing pages 1, 2, 3, 18, 19, 37, 38, 39 of actual document.

View the full content.
View Full Document
View Full Document

symptotic Notation, Review of Functions & Summations

64 views


Pages:
39
School:
University of North Carolina at Chapel Hill
Course:
Comp 550 - Algorithms and Analysis

Unformatted text preview:

Asymptotic Asymptotic Notation Notation Review Review of of Functions Functions Summations Summations January 13 2019 Comp 122 Spring 2004 Asymptotic Complexity Running time of an algorithm as a function of input size n for large n Expressed using only the highest order term in the expression for the exact running time Instead of exact running time say n2 Describes behavior of function in the limit Written using Asymptotic Notation ymp 2 Comp 122 ymp 3 Asymptotic Notation O o Defined for functions over the natural numbers Ex f n n2 Describes how f n grows in comparison to n2 Define a set of functions in practice used to compare two function sizes The notations describe different rate of growth relations between the defining function and the defined set of functions Comp 122 notation For function g n we define g n big Theta of n as the set g n f n positive constants c1 c2 and n0 such that n n0 we have 0 c1g n f n c2g n Intuitively Set of all functions that have the same rate of growth as g n g n is an asymptotically tight bound for f n ymp 4 Comp 122 notation For function g n we define g n big Theta of n as the set g n f n positive constants c1 c2 and n0 such that n n0 we have 0 c1g n f n c2g n Technically f n g n Older usage f n g n I ll accept either f n and g n are nonnegative for large n ymp 5 Comp 122 ymp 6 Example g n f n positive constants c1 c2 and n0 such that n n0 0 c1g n f n c2g n 10n2 3n n2 What constants for n0 c1 and c2 will work Make c1 a little smaller than the leading coefficient and c2 a little bigger To compare orders of growth look at the leading term Exercise Prove that n2 2 3n n2 Comp 122 ymp 7 Example g n f n positive constants c1 c2 and n0 such that n n0 0 c1g n f n c2g n Is 3n3 n4 How about 22n 2n Comp 122 O notation For function g n we define O g n big O of n as the set O g n f n positive constants c and n0 such that n n0 we have 0 f n cg n Intuitively Set of all functions whose rate of growth is the same as or lower than that of g n g n is



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view symptotic Notation, Review of Functions & Summations and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view symptotic Notation, Review of Functions & Summations and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?