What is the time complexity of this algorithm?
Subject Algorithm Design
NU Year Set: 2.(c) Marks: 5 Year: 2009

notation:
To denote asymptotic upper bound, we use O-notation. For a given function g(n), we denote by O(g(n))(pronounced “big-oh of g of n”) the set of functions:
O(g(n))= { f(n) : there exist positive constants c and n0 such that 0≤f(n)≤c∗g(n) for all n≥n0 }

Ω-notation:
To denote asymptotic lower bound, we use Ω-notation. For a given function g(n), we denote by Ω(g(n))(pronounced “big-omega of g of n”) the set of functions:
Ω(g(n))= { f(n) : there exist positive constants c and n0 such that 0≤c∗g(n)≤f(n) for all n≥n0 }

Θ-notation:
To denote asymptotic tight bound, we use Θ-notation. For a given function g(n), we denote by Θ(g(n))(pronounced “big-theta of g of n”) the set of functions:
Θ(g(n))= { f(n) : there exist positive constants c1,c2 and n0 such that 0≤c1∗g(n)≤f(n)≤c2∗g(n) for all n>n0 }

 

 

Login to post your comment.