Can any one get me how is the (log n), (n log n), complexity is calculated with an example code?

- anonymous

Can any one get me how is the (log n), (n log n), complexity is calculated with an example code?

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- katieb

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- mattfeury

are you referring to a specific algorithm? in a lot of cases (such as divide and conquer algorithms like mergesort), the algorithm is recursive and as such can be though of as a binary tree of recursive calls. the height of a complete binary tree (from node to leaf) is log n where n is the number of elements. I can go into more detail later if you have questions and i'm not in class ;)

- rsmith6559

You may want to check the Wikipedia article on "Big O notation" as a starting point.

- anonymous

@mattfeury thanks for the reply, well considering the BST, what will be the complexity for the following operations.
----->Display, Inorder, Preorder and Postorder- For all these we use the recursive call of the display function,
like display(p->left) and printf() and display(p->right)
what will be the time complexity for the above operation
------> Finding a node in the tree, Deleting a node in the tree, Finding how many nodes are present in the tree
-------> finding the depth of the tree
awaiting your reply :) :) :)

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- anonymous

@rsmith6559 ya sure, i will look over that too, thanks for the reply

- mattfeury

i'm making a few assumptions here, especially when it comes to 'deleting'. but here is some info:
----->Display, Inorder, Preorder and Postorder
this would be O(n) I believe. Essentially, we are traversing a tree and printing each element in some order. regardless of the order, we only hit each node/element once. so we make a total of n operations (the operation here is print, i guess).
------> Finding a node in the tree, Deleting a node in the tree, Finding how many nodes are present in the tree
I don't know if these would all be the same, but if they're supposed to be, i'm gonna say they're all O(log n). The length from head to leaf is log n. Since it is a BST, we at most make log n comparisons before we find the element. Deleting a node is as simple as removing it from its parent (although this doesn't account for any rebalancing).
finding the number of nodes could be different depending on if it is a complete tree, buti think it would be O(n). I hope these three didn't have to be the same otherwise I'm wrong.
-------> finding the depth of the tree
as previously mentioned, the depth of a tree is log n

- mattfeury

hmm well that last one could be O(n). if the tree is unbalanced, it will essentially be a linked list which is O(n)

- mattfeury

but that logic would make each answer = O(n)
so i guess you should ask whether they meant a balanced BST or just any BST in general which could worse case be a linked list.

- anonymous

@mattfeury thanks for your reply, but I reckon, in the recursion each node is not just visited once, this is seriously confusing, for the code snippet which gets the display function using recursion i did print some thing and looked over, I ll attach the file which the output look over that too,,,,,,,
void display(struct node *p){
if(p!=NULL){
printf("\n before left:%d add:%d\t",p->data,&p);
display(p->left);
printf("\n after left:%d add:%d\t",p->data,&p);
printf("\n\n data is %d ->\t",p->data);
display(p->right);
printf("\n after right:%d add:%d\t",p->data,&p);
}
else{
printf("\n Exiting");
return;
}
}

##### 1 Attachment

- mattfeury

hmm this seems strange. are you sure yr tree is good?
yr printlns are a bit confusing too. if you do
display(p->left);
printf("\n\n data is %d ->\t",p->data);
display(p->right);
then it should print out a sorted list of the data in the tree.
i could be wrong, but a traversal will never repeat a node unless there is a loop which invalidate the tree and make it a graph.

- anonymous

@mattfeury well I reckon, I need to get U the full code, find the attachment of the full code here...

##### 1 Attachment

- anonymous

@mattfeuty pls ignore that max in the switch, pls consider the ADD and DISPLAY functions alone.....

- mattfeury

well i had to change a few things for my system (make main return int, change the malloc import), but it gave me the in order traversal.
not sure what could be going on on yr end. i added a tree in random order and it came out sorted.

##### 1 Attachment

- anonymous

@mattfeuy well that was awesome, but I don't get Y when we put the printf statements before (p->left), after (p->left) and before (p->right) makes as such the pointer visits the nodes so many times?
well U do the same U will get it, the same result....

- anonymous

@mattfeuty And also we found that the pointers that are created in the recursions, are all same in the breadth wise, i.e. the same pointer is placed in the level 0, and when getting to level 1 we have a single pointer refering all the nodes,
check over the addresses that I printed in there... U will get to know, and also look over the attachment,.

##### 1 Attachment

- mattfeury

FWIW, you need to change your data type for the memory address in the printfs:
change to %p (for pointer)
printf("\n before left:%d add:%p\t",p->data,&p);
i'm thinking you may have a problem with yr add method. you never actually hook the parent up to the new node.

- mattfeury

for instance, maybe have add return a node. then in your else statement (in add), when the next add() (recursion) returns, store it's return value for the current node's left or right.

- anonymous

@mattfeury I may be wrong with my code, but if the adding is not perfect we may not be able to get that sorted node list in the in order(display) function correctly right.... I am sorry if am wrong, can U pls make the change?

- mattfeury

what about this?
struct node* add(struct node **p, int num){
if(*p==NULL){
*p =(struct node *)malloc(sizeof(struct node));
(*p)->data = num;
(*p)->left= NULL;
(*p)->right= NULL;
return *p;
}
else{
if(num>=(*p)->data)
(*p)->right = add(&((*p)->right), num);
else
(*p)->left = add(&((*p)->left), num);
}
return *p;
}
(full code attached. i am running on a mac)

##### 1 Attachment

- mattfeury

when you make the node and return, you then have to set the parent's right/left to be that new node. if a node already exists, it will just return that node and reset it.

- anonymous

@mattfeury cool :) :) well will this solve that recursion visiting more than once?

- anonymous

@mattfeury sorry I dint get U... Y U made this change can U pls explain that?

- mattfeury

it looks fine to me :).
when you add a node, you recurse until you find its proper location in the tree. at this point, we create a new node (malloc) and set its data and return.
after we return back up a level, we need to set the parent node's right or left value to the new node.

- anonymous

@mattfeury if i am not wrong that function will always returns the pointer pointing to the parent right?

- mattfeury

correct.
although since it's recursive, not every call will return the same 'parent' node

- mattfeury

but when i just want to add a node:
add(&head, data)
will recurse add it and return the parent (&head)

- anonymous

@mattfeury fine... thanks for sparing your time :) :) :)

- anonymous

Obviously since In my code when I try passing the address of the head, i create the temproray pointer in there, so then the temp pointer are only gonna do the adding stuff, so there wont be any change to the address of head pointer, so even though U are not returning the pointer of the parent there wont be any changes I reckon?

- anonymous

by temp pointer I mean that, the formal parameter....

- anonymous

@mattfuery getting me? r should I make it clear?

Looking for something else?

Not the answer you are looking for? Search for more explanations.