We're a community of 1.1M IT Pros here for help, advice, solutions, professional growth and fun. Join us!
1,080,650 Members — Technology Publication meets Social Media

# finding nth last element with 0(n) complexity

By Iam3R on Oct 29th, 2009 3:32 pm

I am very poor in calculating complexities.
Please some one let me know what is the complexity of the below program.

I actually want to write a program for finding the nth last element with 0(n) complexity.
but unable write, please give me some idea.

the below code works perfectly and i considered all the posibilities.

``````if list empty : returns zero
if postion is < 0 : returns -2
if position is > no of elements in the list : returns -1``````

please mention if any other possibilities can be covered.

``````// p is position of element to find

int nthlast(struct node *n,int p) {

struct node *f, *s;
if(n) {
int cnt=0;
f = n;// start address store in first pointer
while(n != NULL && cnt<p-1)
n=n->next, cnt++; // move the the pointer p-1 times
if(!n) /* if the entered poistion is greater than the no of elements */
return -1;
if(p <= 0)
return -2; /* if entered poisition is lessthan or equal to zero */
s = n;
while(n)  {
int cnt = 0;
while(n != NULL && cnt < p-1)
n=n->next, cnt++;
if(n) {
f = s;
s = n;
}
else  {
int i=0;
while(i<cnt-1)  {
i++;
f=f->next;
}
return f->data;
}
if(p==1) {
n=n->next;
s = n;
}
}
return f->data;
}
else
return 0;
}

//Driver code:

int main()
{

struct node*p=NULL;
int n,d,i=0,ele,a[10]={1,2,3,4,5,6,7,8,9,10};

while(i<10)
{

insert(&p,a[i++]);
}
display(p);
printf("nter the pos\n");
scanf("%d",&n);
if((ele = nthlast(p,n)) > 0)
printf("\n%d",ele);
else if(!ele)
printf("list empty\n");
else if(ele == -1)
printf("no of elements less than the pos\n");
else
printf("positio shuold be > 0\n");

return 0;
}

inserting elements function:

void insert(struct node**p,int num)
{
if(*p==NULL)
{
(*p)=malloc(sizeof(struct node));
(*p)->next=NULL;
(*p)->data=num;
}
else
{
insert(&((*p)->next),num);
}
}``````
Post: Markdown Syntax: Formatting Help

You