- Finite set of computational instructions
- Set of steps to solve the problem
- Input / output : some input from some standard set of input and must produce output
- Definiteness: each step must be unambiguous
- Finiteness: algorithm must terminate after finite tome or steps
- Correctness: correct set of output values must be provided from each set of inputs
Random Acess Machine Model
- Base machine model for the study of design and analysis of algorithm
- Machine independent environment
- Each basic operation (+, -) takes steps
- Loops and subroutines are not basic operations
- No shortage of memory
a=0; b-1, f=1;
for(i=2; i<=n; i++)
GCD (Greatest Common Divisor)
- Common method to calculate GCD
GCD (4,8)= 2*2*1 =4
- Euclidean algorithm to find GCD
Return GCD (b, a mod b)
No. of basic operation (division)=5
No. of basic operation = 2
Mathematical notations which are used to describe running time of algorithms
- Complexity analysis of the algorithm is very hard if we try to analyse the exact; so its nearby solution
- the complexity of an algorithm is the mathematical function of size of input
- So we analyze the algorithm in terms of upper bound and lower bound
- Mostly we concentrate on worst case only
- Check image [graph wala]
- Three types of asymptotic notation
- Big Oh (O) Notation
- Big Omega (Ω) Notation
- Big Theta (Ꝋ) Notation
- Logab= loaga+logb
- Log(a/b)= loga-logb
- Log (ab) = bloga
- Log1=0; log2=1; log1024=10
Big Oh (O) Notation
- A function f(x)=O (g(x)) iff there exists two positive integers c and no, such that for all n>=no, 0<=c*g(n)<=f(n)
- Represents the upper bound of the running time of an algorithm
- Worst-case complexity of an algorithm can be found with big oh
Prove that f(n)=O(g(n))
Big Omega (Ω) Notation
- A function f(x)=Omega(g(x)) iff there exists two positive integers c and no, such that for all n>=no, 0<=c*g(n)<=f(n)
- represents lower bound
- gives best case of algorithm
Big Theta (Ꝋ) Notation
- A function f(x)= Ꝋ (g(x)) iff there exists three positive constans c1, c2 and no, such that for all n>=no, 0<=c1*g(n)<=f(n)<=c2*g(n)
- See photo
Example (Insertion Sort)
For (i-1; i<n; i++)
while(j>=0 && A[j]>x)
To be continued…
People are Loving
A Complete and Powerful Guide for Google Search Console (GSC) 
Google Search Console (GCS): Google Search Console is a webmaster tools which helps to check the website statistics and index...
Blue Screen Error on Microsoft Surface Pro: Fix it with some Simple Methods
The latest Microsoft Surface Pro models have great functionality. But they’re not immune to the common issues you face in...
8 ways to grow your Tiktok followers and get famous
Are you wondering about how to grow your Tiktok followers? TikTok is one of the latest social media sites, and...
Tips and Tricks to Make Siri More Useful
Everyone has love and hate relationship with Siri. Siri is Apple’s voice controlled digital assistant of iOS. Siri is powered...
How to remove Microsoft Edge from Windows 10?
Browsers Overview Many people use Google Chrome browser, Mozilla Firefox, Microsoft Edge, Safari Browser, and some of the professional user...
10 Hits in 30 Days
Security4 weeks ago
Data Safety on the Cloud – How to Keep your Cloud Storage Safe and Sound
Certification4 weeks ago
Only 4 Steps and Your Certbolt PMI PMP Certification in Your Pocket!
Share Market3 weeks ago
IPO Result of Jeevan Bikash Laghubitta Bittiya Sanstha Limited (JBLBSL). When will JBLBSL IPO Result Publish?
Share Market3 weeks ago
IPO Result of Manakamana Smart Laghubitta Bittiya Sanstha Limited. When will Manakamana Smart Laghubitta IPO Result Publish?
Computer3 weeks ago
People are using these 8 easy tips to stop spam in their mail.
EVENTS3 weeks ago
ICT Award 2021 – Biggest Tech Award of Nepal calls for Nomination
Auto Life7 days ago
Bike Tax Rate in Nepal [ 2078/79 – Latest Update ]
OPINION2 weeks ago
Nest Nepal Hosting Review: Is it worth buying Nest Nepal’s Hosting in Nepal?