Asymptotic Notation - 22 Weeks of DSA

 In the previous post (Click to visit), we have already studied about Best, Average, and Worst-Case. 

Order of Growth: (It's very important)

c < log log n < log n < n^1/3 < n^1/2 < n < n² < n³ < n⁴ < 2ⁿ < nⁿ

Now let's talk about Notations.

There are three types of Notations (mainly):

• BIG O Notation
• BIG OMEGA Notation (Ω) and
• BIG THETA Notation (Θ)

Let's check each one by one...

Big O Notation:

Okay so consider, you have 2 algorithms, one which takes 10 iterations and the other which takes 20 iterations, no issues on that both will have almost the same efficiency, but when it comes to 10 iterations and 1000 iterations, then it is a matter of concern.

The Big O notation, where O stands for 'order of' is concerned with what happens for the huge values of n. For example, if sorting the algorithm performs n*n operations to sort just n elements, then that the algorithm would be described as O(n*n) algorithm. 

When expressing complexity using Big O notation, constant multipliers are ignored. That means an O(4n) is equivalent to O(n). 

If f(n) and g(n) are the functions defined on a positive integer number n, then

f(n) = O(g(n))  --- read as 'f of n is Big O of g of n'

and this is possible if and only if positive constants c and n exists, such that

f(n) ≤ cg(n)

It means that for a large amount of data, f(n) will grow no more than a constant factor than g(n). Hence g provides an upper bound.

Note that here c is a constant which depends on the following factors:

• the programming language used,
• the quality of the compiler or interpreter,
• the knowledge of programmer,
• the size of the main memory and the access time to it,
• the CPU speed, and
• the algorithm itself.

Point to remember: the Big O notation provides a strict upper bound for f(n). That means that function f(n) can do better but not worse then the specified value.

Mathematically speaking, 

        If f(n) ≤ cg(n), c > 0,∀ n ≥ n₀, then f(n) = O(g(n)) and g(n) is an asymptotically tight upper bound for f(n). 

Example of function in O(n³) include n^2.9, n³, n³ + n, 540n³ + 10.

And the examples which not comes in O(n³): n^3.2, n², n²+ n, 540n + 10, 2n.

Big O Notation: f(n) ≤ c g(n)

Categories of Algorithms:

A/c to Big O we have five different categories of algorithms...

• Constant time algorithm: O(1)
• Linear time algorithm: O(n)
• Logarithmic time algorithm: O(log n)
• Polynomial-time algorithm: O(n^k) where k > 1
• Exponential time algorithm: O(2ⁿ).

Limitations of Big O Notation: 

• Many algorithms are simply too hard to analyze mathematically.
• There may not be sufficient information to calculate the behavior of an algorithm in the average class.
• Big O analysis only tells us how the algorithm grows with the size of the problem, not how efficient it is, as it does not consider the programming effort. 
• It ignores important constants. 

Omega Notation (𝛀):

The Omega notation provides a tight lower bound for f(n). This means that the function can ever do better than the specified value but it may be worse.

Ω notation is simply written as f(n) ∈ Ω(g(n)), where n is the problem size and 

Ω(g(n)) = {h(n): ∃ positive constant c > 0, n_o such that 0 ≤ cg(n) ≤ h(n), ∀ n ≥ n₀}.

Hence, we can say that Ω(g(n)) comprises a set of all the functions h(n) that are greater than or equal to cg(n) for all values of n ≥ n_o.

If cg(n) ≤ f(n), c < 0, ∀ n ≥ n_o, then f(n) ∈ Ω(g(n)) and g(n) is an asymptotically tight lower bound. 

Examples of  functions in Ω(n²) include: n², n³+n², n³, n^2.9

Examples of functions not in Ω(n³) include: n², n^2.9, n

Omega Notation: f(n) ≥ c g(n)

To summarize,

• Best Case Ω describes a lower bound for all combinations of input.
• Worst case Ω describes a lower bound for worst-case input combinations.
• If we simply write Ω,  it means the same as best-case Ω.

Theta Notation (Ө):

Theta notation provides an asymptotically tight bound for f(n). Ө notation is simply written as, f(n) ∈ Ө(g(n)), where n is the problem size and 

Ө(g(n)) = {h(n): ョpositive constant c₁, c₂, and n₀ such that 0 ≤ c₁g(n) ≤ h(n) ≤ c₂g(n), ∀ n ≥ n₀}.

Hence, we say that Ө(g(n)) comprises a set of all the functions h(n) that are between c₁g(n) and c₂g(n) for all values of n ≥ n₀.

Theta Notation: c₂ g(n) ≤ f(n) ≤ c₁ g(n)

To summarize,

• The best case in Ө notation is not used.
• Worst case Ө describes asymptotic bounds for the worst-case combination of input values.
• If we simply write Ө, it means the same as worst-case Ө.

In the upcoming post, we will be calculating the complexities of the expressions...

Next: Complexity Analysis in loops

By that,

Harsh Jaiswal

Signing of...

Analysis of Algorithm - 22 Weeks of DSA

DAY - 01 of 22 Weeks

View the plan Here...

Analysis of Algorithm...

The typical definition of an algorithm is 'a formally defined procedure for performing some calculation'. If a procedure is formally defined, then it can be implemented using formal language, and such language is known as a programming language. In general terms, the algorithm provides a blueprint to write a program to solve a particular problem. 

TIME and SPACE Complexity

Analyzing an algorithm means determining the number of resources (such as time and memory) needed to execute it. Algorithms are generally designed to work with an arbitrary number of inputs, so the efficiency or complexity of an algorithm is stated in terms of time and space complexity. 

The time complexity of an algorithm is basically the running time of a program as a function of the input size. Similarly, the space complexity of an algorithm is the amount of computer memory that is required during the program execution as a function of the input size.

The running time/execution time depends on several factors. First, the amount of data that must be processed directly affects the execution time. As the data size increases, so does the execution time. Second, the execution time can vary depending on the type of hardware and the time the computer is used. If we use a multi-process, multi-user system to execute the program, the execution of other programs on the same machine can directly affect the execution time of our program. Finally, the choice of programming language and compiler used to implement an algorithm can also influence the execution time. Some compilers are better optimizers than others and some languages produce better-optimized code than others.

Thus, we need a method to analyze an algorithm's efficiency independent of the implementation details.

Worst-case, Average-case, Best-case, and Amortized Time Complexity

Worst-Case running time: 

• This denotes the behavior of an algorithm with respect to the worst possible case of the input instance.
• This case of an algorithm is an upper bound on the running time for any input.
• Having the knowledge of worst-case gives an assurance that the algorithm will never go beyond this time limit.

Average-Case running time:

• Average-Case running time is an estimate of the running time for an 'average' input. 
• Average-case running time assumes that all inputs of a given size are equally likely.

Best-Case running time:

• This case is used to analyze an algorithm under optimal conditions. For example, the best case for the linear search of an array occurs when the desired element is the first in the list. 
• While selecting an algorithm we hardly base our decision on the best-case performance. 

Amortized running time:

• Amortized running time refers to the time required to perform a sequence of (related) operations averaged over all the operations performed. 
• Amortized analysis guarantees the average performance of each operation in the worst case.

Expressing Time and Space Complexity

The time and space complexity can be expressed using the function f(n) where n is the input size for a given instance of the problem being solved. 

Expressing the complexity is required when 

• We want to predict the rate of growth of complexity as the input size of the problem increases.
• There are multiple algorithms that find solutions to a given problem and we need to find the most efficient algorithm.

Algorithm Efficiency

If a function is linear (without any loops or recursion), the efficiency of that algorithm or running time of that algorithm can be given as the number of instructions it contains.

Algorithm efficiency changes with change in the number of loops. 

Linear Loops

To determine an efficiency of algorithm with single loops, we first need to calculate the number of times the statement in the loops will be executed.

This is because, Number of iteration is directly proportional to the loop factor.

Example:

In C :

for (i = 0; i < 500; i++)
    statement block;

In Python:

for i in range(0, 500):
    statement block

Here, 500 is the loop factor. 

As we know now, efficiency is directly proportional to number of iterations. So, the general formula in the case of linear loop can be written as :

f(n) = n

Nevertheless calculating efficiency is not so simple as in above example.

Consider the given loop...

In C:

for (i = 0; i < 500; i += 2)
    statement block;

In Python:

for i in range(0, 500, 2):
    statement block

Here, the number of iteration is half the number of loop factor. So efficiency is given as,

f(n) = n/2

Logarithmic Loops

Now we know, what are linear loops, they are whose loop updates either by addition or subtraction. Anyway, in logarithmic loops, the loop-controlling variable is either multiplied or divided during each itetration of the loop. As shown below...

In C:

for (i = 1; i < 1000; i *= 2)                for (i = 1000; i >= 1; i/=2)
    statement block;                             statement block;

In Python:

for i in range(1, 1000):                     for i in range(1000, 1, i/2):
    statement block                              statement block

Consider the first for loop in which the loop-controlling variable i is multiplied by 2. The loop is executed only 10 times and not 1000 times because in each iteration the value of i doubles.

And in the second loop in which the loop-controlling variable i is divided by 2. In this case also, the loop will be executed 10 times. 

Thus, the number of iteration is a function of the number by which the loop-controlling variable is divided or multiplied.

That is, when n = 1000, the number of iterations canbe given by log 1000 which is approximately equal to 10.

Therefore, when loop-controlling variable is divided or multiplied then, then efficiency is given as,

f(n) = log n

Nested Loops

Loops inside loops are Nested Loops. To determine the efficiency of Nested loops, we need to calculate the number of times each loop is multiplied after each iteration. The total is then obtained as theproduct of the number of iterations in both loops.

Linear logarithmic loop

Consider the following loops:

In C:

for (i = 0; i < 10; i++)            -- (n) times
    for (j = 1; j < 10; j *= 2)        -- (log n) times
        statement blocks;

In Python:

for i in range(0, 10):            -- (n) times
    for j in range(1, 10):        -- (log n) times
        statement blocks;
        j *= 2;

So, the efficiency is f(n) = n log n.

Quadratic loop

Consider the following loops:

In C:

for (i = 0; i< 10; i++)            -- n times
    for (j = 0; j < 10; j++)        -- n times
        statement block;

In Python:

for i in range(0, 10):                -- n times
    for j in range(0, 10):            -- n times
        statement block

So, the efficiency is f(n) = n^2.

Dependent quadratic loop

In dependent quadratic loop, the number of iterations in the inner loop is dependent on the outer loop. Consider the following loop:

In C:

for (i =0; i < 10; i++)
    for (j = 0; j <= i; j++)
        statement block; 

In Python:

for i in range(0, 10):
    for j in range(0, i+1):
        statement block

So, the efficiency is calculated as:

1+2+3+4+...+9+10 = 55

So, we have f(n) = n (n + 1) / 2

Next: Asymptotic Notation

See you in the next post.

Its Harsh Jaiswal

Signing off...