When it comes to Gate, one or two question is always expected from this topic. This article will help to solve questions on **Asymptotic Notation** quickly and efficiently.

The efficiency of algorithm can be determined by time or space required by algorithm.Asymptotic notations are used to represent the relative growth rate between functions.There are major 3 parameters to measure their efficiency.

Big OH (upper bound)

Big Omega (lower bound)

Theta ( Tight bound)

**Big-OH**

It represents the upper bound on the running time and memory being consumed by the algorithm.O(n) essentially conveys that the growth rate of running time will not be more than n.

If f(n) = O(g(n))

then f(n) ≤ c.g(n)

f(n) = O (g(n)) , it means growth rate of function g(n) is higher / equal to f(n)

if h(n)= O(p(n))

f(n) + h(n) = O (max(g(n)), h(n)))

**must read : 6 Month Study Plan/TimeTable To Crack GATE (CS) 2017 By Experts **

**Big Omega(Ω) **

It represents the lower bound on the running time and memory being consumed by the algorithm.Ω(n) conveys that growth rate will not be less than n for all inputs of size n

f(n) & g(n) are 2 functions

if f(n) is Ω g(n), f(n) ≥ c.g(n)

If f(n) is O(g(n)), then g(n) is Ω (f(n))

**Theta Notation (ϴ) **

It represents tight bound on running time

f(n) & g(n)

f(n) = c.g(n) for x > x_{0}

f(n) = ϴ {g(n)}

if f(n) = ϴ {g(n)}, growth rate of function g(n) is surely equal to f(n), not less and not more than f(x).

**Important Article :** Strategy to Prepare for GATE by Self-Study/Without Coaching by experts

**Tips for solving Questions On Asymptotic **

**#Tip1 **

One should remenber the general order of following functions.

**O(1) < O(logn) < O( n) < O( nlogn) < O(n*n) < O(n*n*n) < O(n ^{k})< O(2^{n})**

**#Tip2**

if f(x) = ϴ (g(x)) , we can say that f(x) is O(g(x)) and f(x) is Ω(g(x))

and also g(x) is O(f(x)) and Ω(f(x))

**must read : Most Important Topics For GATE-2017 (CSE) || guaranteed Results**

**#Tip3**

The running time of for/while loop is number of iterations * running time of statement inside loop.

int sum=0;

for (int i=0;i<n;i++)

{

Sum=sum +i,

}

The running time is O(n)

→

**#Tip4**

For nested loop

The running time of statement inside group of nested loop is product of size of loops.

for (i=0; i<n; i++)

for (j=0; j<k; j++)

a++;

The running time is O(n×k)

** Also read : Proven Preparation Strategies by GATE 2015 CSE Topper (AIR 63)**

**#Tip5**

sum of statements:

Add running time of all the statements

for (i=0;i<n; i++)

k++ → O(n)

for (j=0; j<n; j++)

for (t=0, t<n; t++)

The running time is 0(n) + 0(n^{2})

**#Tip6 **

**Recursive function**

Derive recurrence relation and then solve it ,getting the running time is always better way than other structure.

→ Suppose T(n) is running time of function ABC and the variable reduces to half in next call.

T(n) = T(n/2) + complexity rest of code

** must read : Experts Tips to Solve NP-Complete Problems in GATE 2017 **

**#Tip7**

An algorithm is O(log n) if it takes constant time to cut problem of half.

Like binary score, heap.

**# T(sqrt(n )) → O(loglog n) **

where T is recurrence relation

**Examples from GATE :**

**GATE 2007**

int doSomething (int n) { if (n≤ 2)

return 1;

else

return doSomething ( floor(sqrt (n)) + n)

}

GATE-2017 Preparation

Start Quiz

**Solution**

T(n) = T(sqrt(n)) + 1

O(loglogn)

**Question :**

Sum=0

for (i=0; i< n; i++)

for (j=0;j<i*i;j++)

for(k=0;k<j;k++)

sum++;

**Solution **

It like

O(n × n^{2} × n^{2})

=O(n^{5})

You can count the number of iterations replacing n=4.

**Best Wishes !!**

What aspirants need is the right approach along with concrete strategies to reach their goals. **GATE GUARANTEE PACK has been the choice of successful GATE toppers all over India. **

It is the perfect online tool to check your level of preparedness among st students preparing all over the country where you study under guidance of mentors.