Skip to main content

Algorithms language Chapter 2: Algorithm Complexity (Part-1)

Chapter 2: Algorithm Complexity


Section 2.1: Big-Theta notation

Unlike Big-O notation, which represents only upper bound of the running time for some algorithm, Big-Theta is a
tight bound; both upper and lower bound. Tight bound is more precise, but also more difficult to compute.

The Big-Theta notation is symmetric: f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))

An intuitive way to grasp it is that f(x) = Ө(g(x)) means that the graphs of f(x) and g(x) grow in the same rate, or
that the graphs 'behave' similarly for big enough values of x.

The full mathematical expression of the Big-Theta notation is as follows:

Ө(f(x)) = {g: N0 -> R and c1, c2, n0 > 0, where c1 < abs(g(n) / f(n)), for every n > n0 and abs is the absolute value }

An example

If the algorithm for the input n takes 42n^2 + 25n + 4 operations to finish, we say that is O(n^2), but is also O(n^3)
and O(n^100). However, it is Ө(n^2) and it is not Ө(n^3), Ө(n^4) etc. Algorithm that is Ө(f(n)) is also O(f(n)), but
not vice versa!

Formal mathematical definition

Ө(g(x)) is a set of functions.

Ө(g(x)) = {f(x) such that there exist positive constants c1, c2, N such that 0 <= c1*g(x) <= f(x)
<= c2*g(x) for all x > N}

Because Ө(g(x)) is a set, we could write f(x) ∈ Ө(g(x)) to indicate that f(x) is a member of Ө(g(x)). Instead, we
will usually write f(x) = Ө(g(x)) to express the same notion - that's the common way.

Whenever Ө(g(x)) appears in a formula, we interpret it as standing for some anonymous function that we do not
care to name. For example the equation T(n) = T(n/2) + Ө(n), means T(n) = T(n/2) + f(n) where f(n) is a
function in the set Ө(n).

Let f and g be two functions defined on some subset of the real numbers. We write f(x) = Ө(g(x)) as
x->infinity if and only if there are positive constants K and L and a real number x0 such that holds:

K | g(x)| <= f(x) <= L | g(x)| for all x >= x0.

The definition is equal to:

f(x) = O(g(x)) and f(x) = Ω(g(x))

A method that uses limits

if limit(x->infinity) f(x)/g(x) = c ∈ (0,∞) i.e. the limit exists and it's positive, then f(x) = Ө(g(x))

Common Complexity Classes

Name         Notation       n = 10        n = 100
Constant      Ө(1)            1             1
Logarithmic   Ө(log(n))       3             7
Linear        Ө(n)            10            100
Linearithmic  Ө(n*log(n))     30            700
Quadratic     Ө(n^2)          100           10 000
Exponential   Ө(2^n)          1 024         1.267650e+ 30
Factorial     Ө(n!)           3 628 800     9.332622e+157
Labels:

Comments

Post a Comment

Popular posts from this blog

Object-Oriented Programming (OOPS)

 Object-Oriented Programming (OOPS) OOPS stands for "Object-Oriented Programming" and is a programming paradigm that focuses on the creation and manipulation of objects. In object-oriented programming, software is organized around objects, which are instances of classes that encapsulate data and behavior. The main principles of object-oriented programming include: Encapsulation: Objects encapsulate data and behavior together, hiding the internal details and exposing a public interface for interacting with the object. Inheritance: Classes can inherit properties and methods from other classes, forming a hierarchy of classes. Inheritance allows for code reuse and the creation of specialized classes based on existing ones. Polymorphism: Polymorphism allows objects of different classes to be treated as objects of a common superclass. This enables the use of generic code that can operate on objects of different types, providing flexibility and extensibility. Abstraction: Abstractio...
Post a Comment
Read more

Cascading Style Sheets (CSS) Programming Language

  CSS (Cascading Style Sheets) is a programming language used for styling and formatting the appearance of web pages. It works in conjunction with HTML to define the visual presentation of elements on a website. Here are some key points about CSS: Selectors: CSS uses selectors to target specific HTML elements and apply styles to them. Selectors can be based on element types, class names, IDs, attributes, or other criteria. Properties and Values: CSS properties define the visual aspects of elements, such as color, size, position, and font. Each property has a corresponding value that specifies how the property should be applied. For example, the color property sets the text color, and the value can be a named color or a hexadecimal code. Style Rules: CSS style rules consist of a selector and one or more property-value pairs enclosed in curly braces. Multiple style rules can be combined to target different elements or groups of elements on a page. External, Internal, and Inline CSS:...
Post a Comment
Read more

Block Chain : A Practical Guide To Developing Business, Law And Technology Solutions

  Block Chain : A Practical Guide To Developing Business, Law And Technology Solutions  Blockchain is a decentralized digital ledger technology that allows multiple parties to record and verify transactions in a secure and transparent manner. It was originally introduced as the underlying technology for Bitcoin, the first cryptocurrency, but its applications have since expanded beyond digital currencies. At its core, a blockchain is a chain of blocks, where each block contains a list of transactions. These blocks are linked together using cryptographic hashes, creating an immutable and tamper-resistant record of all transactions. Here are some key characteristics of blockchain: Decentralization: Unlike traditional centralized systems, blockchain operates in a decentralized manner. It is maintained by a network of computers, known as nodes, which collectively validate and store transactions. This distributed nature makes the blockchain resistant to single points of failure and ...
Post a Comment
Read more