Algorithm and Data Stucture

Har dushanba soat 20:30 da boshlashga harakat qilamiz!

Dushanba kunidan boshlab yuqoridagi tartibda kamida 7 ta masalani bitta meeting ni ochib muhokama qilishni boshlaymiz

Asymptotic notations

There are mainly 3 types of Asymptotic notations:

1. Big-O notation: The Big-O notation describes the worst-case running time of an algorithm. It is computed by counting the number of operations it will take in the worst-case scenario with the input ‘n’.

O(g(n)) = { f(n): there exist positive constants c and n0
such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }


2. Big Omega() notation: The notation describes the best running time of an algorithm. It is computed by counting the number of operations it will take in the best-case scenario with the input ‘n’.

Ω(g(n)) = { f(n): there exist positive constants c and n0
such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }


3. Big Theta() Notation: The theta notation encloses the function from above and below, therefore it defines the exact asymptotic behaviour. The notation is used for analyzing the average runtime of an algorithm.

Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0
such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 }

#asymptotic #notation

Model / Machine

1 unit of time for arithmetic and logical operation

1 unit of time for assignment and return statement

#calculate #complexity #time

How to analyse time complexity?

Running time of an algorithm depends upon various factors
1. Single and multiple processor❌
2. Read or write speed ❌
3. 32 or 64 bit architecture ❌
4. Configuration of the machine ❌
5. Input 👈 ✅

We need to evalute time as a function of input




#time #complexity