EBK DATA STRUCTURES AND ALGORITHMS IN C
EBK DATA STRUCTURES AND ALGORITHMS IN C
4th Edition
ISBN: 9781285415017
Author: DROZDEK
Publisher: YUZU
Question
Book Icon
Chapter 2, Problem 6E
Program Plan Intro

Asymptotic Notations:

In asymptotic analysis of algorithms, mathematical tools are used to represent time complexity of algorithm.

  • such mathematical tools are known as Asymptotic notations. Some of the asymptotic notations are
    • Big-O.
    • Big Theta

Big-O:

A function “g(n)” is O(f(n)) if there exists a constant c > 0 such that cf(n) grows faster than “g(n)” for all n>=n0 , that is, “g(n)” is O(f(n)) iff for some constants “c” and "n0", g(n)<=cf(n) for all n>=n0. Here, “f(n)” denotes the upper bound for “g(n)”. The above statement can be read as follows :

  • “n” is size of data set
  • “f(n)” denotes a function calculated while taking n as parameter
  • O(f(n)) means that curve denoted by “f(n)” is an upper bound for a function’s need for resources.

Big Theta:

A function “g(n)” is Θ(f(n)) iff two positive constants “c1” and “c2” and a positive integer "n0" exists such that c1f(n)g(n)c2f(n) for all n>=n0, that is, “f(n)” denotes exact bound for “g(n)”, which denotes that growth rate of “g(n)” and “f(n)” are equal. The above statement can be read as follows :

  • “n” is size of data set
  • “f(n)” denotes a function that is been calculated taking “n” as parameter
  • Θ(f(n)) means that curve denoted by “f(n)” is an exact bound for a function’s need for resources.

Explanation of Solution

b) f(n) + g(n) is Θ(min(f(n),g(n)))

Explanation:

  • Take f(n) = n and g(n) = 1/n.
  • Now, f(n)+ g(n)&

Explanation of Solution

c) 2na is O(2n)

Explanation:

  • The function 2na is not O(2n), as there is no constant c 2na/2n= 2n(a-

Blurred answer
Students have asked these similar questions
I need help to solve the following case, thank you
hi I would like to get help to resolve the following case
Could you help me to know  features of the following concepts: - defragmenting. - dynamic disk. - hardware RAID
Knowledge Booster
Background pattern image
Similar questions
SEE MORE QUESTIONS
Recommended textbooks for you
Text book image
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Text book image
Operations Research : Applications and Algorithms
Computer Science
ISBN:9780534380588
Author:Wayne L. Winston
Publisher:Brooks Cole
Text book image
Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage
Text book image
Systems Architecture
Computer Science
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Cengage Learning
Text book image
COMPREHENSIVE MICROSOFT OFFICE 365 EXCE
Computer Science
ISBN:9780357392676
Author:FREUND, Steven
Publisher:CENGAGE L
Text book image
C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr