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.

 

Free All India Test Equipped with Artificial Intelligence

Start Test  

 

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))

Free All India Test Equipped with Artificial Intelligence

Start Test  

 

Theta Notation (ϴ)

It represents tight bound on running time

f(n) & g(n)

f(n) = c.g(n) for x > x0

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(nk)< O(2n)

 

#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)

Free All India Test Equipped with Artificial Intelligence

Start Test  

#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(n2)

#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)

}

FREE Daily Quiz on Computers for
GATE-2017 Preparation
 
FREE Daily Quiz on Computers for GATE-2017 Preparation.
Start Quiz  

Solution

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

O(loglogn)

 

Free All India Test Equipped with Artificial Intelligence

Start Test  

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 × n2 × n2)

=O(n5)

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.

 

Search on PrepLadder