Define big theta notation, Data Structure & Algorithms

Define Big Theta notation

Big Theta notation (θ): The upper and lower bound for the function 'f' is given by the big oh notation (θ). Considering 'g' to be a function from the non-negative integers to the positive real numbers, we describe θ(g) as the set of function f  such that  for some real constant c1 and c2 >0 and some non negative integers constant n0 , c1g(n)≤f f(n)≤c2g(n) for all n≥n0.  Mathematically, θ(g(n))={f(n): there exists positive constants c1 and c2 like that c1g(n)≤f f(n)≤c2g(n) for all n, n≥n0} , we say "f is oh of g"


Posted Date: 5/10/2013 3:12:47 AM | Location : United States

Your posts are moderated
Related Questions
Explain what are circular queues? Write down routines required for inserting and deleting elements from a circular queue implemented using arrays.           Circular queue:

Example 3: Travelling Salesman problem Given: n associated cities and distances among them Find: tour of minimum length that visits all of city. Solutions: How several

After learning this, you will be able to: understand the concept of algorithm; understand mathematical foundation underlying the analysis of algorithm; to understand se

Q. Define the sparse metrics and also explain the representation of a 4X4 matrix using linked list.         Ans: A matrix in which number of zero entries is quite h

After going through this unit, you will be able to: • define and declare Lists; • understand the terminology of Singly linked lists; • understand the terminology of Doubly

What are stacks? A stack is a data structure that organizes data similar to how one organizes a pile of coins. The new coin is always placed on the top and the oldest is on the

Here,  m represents the unordered array of elements n  represents number of elements in the array and el  represents the value to be searched in the list Sep 1: [Initialize]

Illustrates the program for Binary Search. Program: Binary Search /*Header Files*/ #include #include /*Functions*/ void binary_search(int array[ ], int value,

What is binary search?   Binary search is most useful when list is sorted. In binary search, element present in middle of the list is determined. If key (the number to search)

A useful tool which is used for specifying the logical properties of a data type is called the abstract data type or ADT. The term "abstract data type" refers to the fundamental ma