Complexity

The complexity measure the quantity of resources used by an algorithms as a function of the problem size. One is especially interested in the trend of the complexity when the problem size becomes large, tends towards infinity.

Time Complexity –

How to choose an algorithm and/or a data
structure representation?
1. Effort for implementing the algorithm:
1.1. searching the literature
1.2. programming
1.3. testing
1.4. maintenance
2. Resources used for running the algorithm:
2.1. time (of computation)
2.2. space (in memory)
2.3. energy (number of processors)

Time complexity means to time taken to execute an algorithm. An algorithm should be much time efficient. Time complexity is calculated by counting the no. of elementry functions. Usually take the possibility as worst case.
Calculation of time complexity is done in 4 notations : :-

1- O Notation :  In this we take every possible condition which slows our program, “the worst case” is notifies by Big O Notation.
2- Omega Notation : Function that grows atleast as fast from expression.
3- Theta Notation : Consist of all function lies in both O and Omega.

eg :

f(n) = 3*n^2 + 4*n + 5

The worst case here is defined by theta(n^2) . Same as it can be defined as O(n^2) and Omega(n^2).

Space Complexity : An amount of memory is required at the time of execution for every program. We have to define a memory efficient algo for use at multiple systems.
Every programs divide its space in three parts:

1: Instruction Space : The space required to store the program in Memory. This space is fixed and depends upon number of line of code, iterators and algos.

2: Data Space : It is the space required to store all the variables and data defined in programs, which can be stored in memory or RAM as well.

3: Environment Space : Its the space required to store the program needed to resume function.

DATA STRUCTURE

Data Structure – Data Structure is a way of collecting and organising data in such a way that we can perform operations on these data in an effective way. Data structure is about to rendering element which are organised under some relationship.

We can organise daata such as they have a relation b/w them. Like if we have NAME=“TANMAY” with SALARY=”60,000” then here is a relation developed between TANMAY and 60,000.

Data Structure is program to store structured data which have relations between them.

There are two types of data structures-

1- Primitive Data Structure : Anything we stored whether it is integer, float, char all are considered as premitive data structure.
2- Abstract Data Structure : Array and Complex Data structures, which are used to store large amount of data within a structure is known as abstract data structure . Types are –

1. Linked List
2. Tree
3. Graph
4. Stacks
5. Queue

Algorithm – Algorithm is a set of instruction which are written in order to manipulate the data stored in data structure. It can be defined by flowchart or pseudocode. It is an informal language to define the programs.

An algorithm should be fast and memory efficient. an efficiency of algorithm is defined by –

1- Time Complexity
2- Space Complexicity.

Next Thing will be discussed in next post. 🙂

structure : DS

Structure –  Structure is a collection of different data type. In a structure we can define any data type and can store the related value in that.

struct employee
{
     int uid;
     char name[10];
     ………………..
     ………………..
     int reg;
};

In above program we use to store the data of employee as Unique ID, Name etc, which can be use further to get data.

main()
{
     struct employee obj;
     cout<<”\nENTER NAME : “<<obj.uid;
     …………………………….
     …………………………….
}

As defined above we can access a data obj.uid  defined in a structure.

A sample program is here to describe the structure with pointer…….

#include<iostream.h>
#include<conio.h>
using namespace std;
struct student
{
           int roll;
           long int reg;
           char name[25];
};
int str_disp(struct student *ptr)
{
	cout<<"\nNAME : "<<ptr->name;
	cout<<"\nROLL NO. : "<<ptr->roll;
	cout<<"\nREGISTRATION NO. : "<<ptr->reg;
}
int main()
{
    struct student b;
    cout<<endl;
    cout<<"\nName: ";
    cin>>b.name;
    cout<<"\nRoll no.: ";
    cin>>b.roll;
    cout<<"\nREGISTRATION NO.: ";
    cin>>b.reg;
    str_disp(&b);
    cout<<"\n\nPROGRAMMING AT C#ODE STUDIO";
    getch();
}

POINTERS : DATA STRUCTURE

Pointers – Pointers are use to give reference to the same data type in which a pointer is initialized. Pointer is also used to store an address of variable.

For More –https://codstudio.wordpress.com/2013/10/02/pointers-2/

#include"conio.h"
#include"iostream"
using namespace std;
int main()
{
    int **a;
    int i,j;
    a=new int*[3]; //ALLOCATION OF ARRAY OF SIZE 3
    for(i=0;i<3;i++)
        a[i]=new int[3]; //ALLOCATION OF ARRAY OF SIZE 3
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
        {
            cout<<"\nEnter <"<<i<<"><"<<j<<"> :";
            cin>>a[i][j]; 
        }
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
        {
            cout<<"\nValues <"<<i<<"><"<<j<<"> :";
            cout<<a[i][j]<<endl;
        }
    cout<<"\nPROGRAMMING @ C#ODE STUDIO";
    getch();
    return 0;
}