Introduction to complexity of algorithm

“How will you calculate complexity of algorithm” is very common question in interview.How will you compare two algorithm? How running time get affected when input size is quite large? So these are some question which is frequently asked in interview.In this post,We will have basic introduction on complexity of algorithm and also to big o notation

What is an algorithm?

An algorithm is step by step instructions to solve given problem.
Lets take a simple example.You want to write an algorithm for listening particular song.
1) Search for song on computer.
2) Is song available?
            i.If Yes,Then listen that song.
           ii.If no,download that song and then listen that song.
So we are solving a problem by step by step procedure.This step by step instructions is called Algorithm.

Why do you need to evaluate an algorithm?

You need to evaluate an algorithm so that you can find most optimize algorithm for solving given problem and also considering various factors and constraints.
For example:
You want to go from city A to City B.Then there are various choices available i.e. by flight,bus or train.So you need to choose among different options depending on your budget and urgency.

Counting number of instructions:

Number of instructions can be different for different programming languages.
Lets count number of instruction for searching a element in a array.
Let’s assume our processor takes one instruction for each of the operation:

  • For assigning a value to a variable
  • For comparting two values
  • Multiply or addition
  • Return statement

In Worst case:

If element which we want to search is last element in sorted array then it will be worst case here.
So :
Hence f(n)=3n+3

Asymptotic behaviour :

Here We will see how f(n) performs with larger value of n.Now in above function, we have two parts i.e. 3n and 3. Here you can note two points:
  • As n grows larger, we can ignore constant 3 as it will be always 3 irrespective of value of n. It makes sense as you can consider 3 as initialization constant and different language may take different time for initialization.So other function remains f(n)=3n.
  • We can ignore constant multiplier as different programming language may compile the code differently. For example array look up may take different number of instructions in different languages. So what we are left with is f(n)=n

How will you compare algorithms?

You can compare algorithms by its rate of growth with input size n
Lets take a example.For solving same problem, you have two functions:
f(n) =4n^2 +2n+4 and f(n) =4n+4
For f(n) =4n^22 +2n+4
so here
f(1)=4+2+4
f(2)=16+4+4
f(3)=36+6+4
f(4)=64+8+4
….
As you can see here contribution of n^22 increasing with increasing value of n.So for very large value of n,contribution of n^2 will be 99% of value on f(n).So here we can ignore low order terms as they are relatively insignificant as described above.In this f(n),we can ignore 2n and 4.so
n^2+2n+4 ——–>n^2
For f(n) =4n+4
so here
f(1)=4+4
f(2)=8+4
f(3)=12+4
f(4)=16+4
….
As you can see here contribution of n increasing with increasing value of n.So for very large value of n,contribution of n will be 99% of value on f(n).So here we can ignore low order terms as they are relatively insignificant.In this f(n),we can ignore 4 and also 4 as constant multiplier as seen above so
4n+4 ——–>nSo here n is highest rate of growth.
Point to be noted :
We are dropping all the terms which are growing slowly and keep one which grows fastest.

Big O Notation:

This notation is used for theoretical measure of  execution  of an algorithm. It gives tight upper bound of a given function. Generally it is represented as f(n)=O(g(n)) and it reads as “f of n is big o of g of n”.
Formal definition:
f(n) = O(g(n)) means there are positive constants c and n0, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0. The values of c and n0 must not be depend on n.
When you say O(g(n)) , It means it will never be worst than g(n). Having said that it means O(g(n)) includes smaller or same order of growth as g(n).
So O(n) includes O(n),O(logn) and O(1).

So O(g(n)) is a good way to show complexity of algorithm.

Lets take some example and calculate value for c and n0.
1. f(n)=4n+3
Writing in a form of f(n)<=c*g(n) with f(n)=4n+3 and g(n)=5n

4n+3<=5n for n0=3 and c=5.

or 4n+3<=6n for n0=2 and c=6
Writing in a form of f(n)<=c*g(n) with f(n)=4n+3 and g(n)=6n
so there can be multiple values for n0 and c for which f(n)<=c g(n) will get satisfied.

2. f(n)=4n^2+2n+4
Writing in a form of f(n)<=c*g(n) with f(n)=4n^2 +2n+4 and g(n)=5n^2
4n^2 +2n+4<=5n^2 for n0=4 and c=5

Rules of thumb for calculating complexity of algorithm:

Simple programs can be analyzed using counting number of loops or iterations.

Consecutive statements:
We need to add time complexity of consecutive statements.
f(n)=c1+c2;
So O(f(n))=1

Calculating complexity of a simple loop:

Time complexity of a loop can be determined by running time of statements inside loop multiplied by total number of iterations.

f(n)=c2*n+c1;
So O(n)=n

 
Calculating complexity of a nested loop:

It is product of iterations of each loop.

f(n)=c2*n*n + c1
So O(f(n))=n^2

 
If and else:

When you have if and else statement, then time complexity is calculated with whichever of them is larger.

f(n)=c1+c2+c3+(c4+c5+c6)*n
So o(f(n))=n

Logarithmic complexity

Lets understand logarithmic complexity with the help of example.You might know about binary search.When you want to find a value in sorted array, we use binary search.

Now let’s assume our soreted array is:

and we want to search for 74 in above array. Below diagram will explain how binary search will work here.

When you observe closely, in each of the iteration you are cutting scope of array to the half. In every iteration, we are overriding value of first or last depending on soretedArray[mid].
So for
0th iteration : n
1th iteration: n/2
2nd iteration n/4
3rd iteration n/8.
Generalizing above equation:
For ith iteration : n/2i

So iteration will end , when we have 1 element left i.e. for any i, which will be our last iteration:
1=n/2i;
2i=n;
after taking log
i= log(n);
so it concludes that number of iteration requires to do binary search is log(n) so complexity of binary search is log(n)
It makes sense as in our example, we have n as 8 . It took 3 iterations(8->4->2->1) and 3 is log(8).
So If we are dividing input size by k in each iteration,then its complexity will be O(logk(n)) that is log(n) base k.

Lets take an example:

Complexity of above code will be O(log(n)).

Exercise:

Lets do some exercise and find complexity of given code:

1.

Ans:

Complexity will be O(n)

2.

Ans:

Complexity will be :n+n*n —>O(n^2)

3.

Ans:

Complexity will be n*n/2*log(n)–> n^2log(n)

 4.

Ans:

Complexity will be n/2*n/2*n –> n^3

Was this post helpful?

Related Posts

  • Count files in folder in PowerShell
    01 January

    PowerShell – Count Files in Folders

    Table of ContentsCount Files in Folders in PowerShellCount Files in multiple Folders in PowerShellCount Files in Folders and Subfolders in PowerShellCount only folders inside folder in PowerShellCount Files by Extension in Folder in PowerShell Count Files in Folders in PowerShell We can use the Measure-Object cmdlet in different ways to meet our project requirements. However, […]

  • Check if Object contains property in PowerShell
    31 December

    Check if Object has Property in PowerShell

    Table of ContentsUsing the -match ParameterUsing -contains ParameterUsing if-else BlockUsing .Match() Function with if-else BlockUsing Get-Member Cmdlet Using the -match Parameter Use the -match parameter to check if an object has a property in PowerShell. [crayon-63b307e47ddf0059156021/] [crayon-63b307e47ddf7367003578/] Here, we used the -match parameter to check if the given object, which is $result in our case, […]

  • Create Empty File in PowerShell
    28 December

    Create Empty File in PowerShell

    Table of ContentsUsing New-Item CmdletUse the ni AliasUsing Out-File CmdletUsing the fsutil file CommandUsing Text EditorUsing echo CommandUsing for Loop Using New-Item Cmdlet Use the New-Item cmdlet to create an empty .txt file in PowerShell. [crayon-63b307e47e552271775240/] [crayon-63b307e47e558955293674/] We used the New-Item cmdlet with -Path, -Name, and -ItemType parameters to create an empty .txt file using […]

  • 27 December

    Run PowerShell as Another User

    Table of ContentsUsing the runas CommandOpen the PowerShell as an AdministratorRun the runas commandUsing the Start-Process cmdlet with the Credential ParameterUI-Based SolutionScript-Based Solution Using the runas Command The runas command in PowerShell launches programs using credentials different from the current user. It provides users with limited privileges to execute commands or access resources available only […]

  • 27 December

    Create Array of All NaN Values in Python

    Table of ContentsUsing numpy.empty() FunctionUsing numpy.full() FunctionUsing numpy.tile() FunctionUsing numpy.repeat() FunctionUsing Multiplication of numpy.ones() with nan Using numpy.empty() Function To create an array of all NaN values in Python: Use numpy.empty() to get an array of the given shape. Assign numpy.nan to every array element using the assignment operator (=). [crayon-63b307e47f1d2899707172/] [crayon-63b307e47f1d9145093282/] We used numpy.empty() […]

  • 27 December

    Call Function from Another Function in Python

    Table of ContentsCall a Function in PythonCall Function from Another Function in PythonCall a Function from Another Function within the Same/Different Classes Call a Function in Python To call a function in Python: Write a test() function, which prints a message. Call the function defined in the previous step. [crayon-63b307e47f3c8510897312/] [crayon-63b307e47f3cb790365600/] To call a function, […]

Comments

  1. superb explanation.I went through many explanations to understand time complex before this.But couldnt understand.thankyou soo much for this explanation

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.