A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

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

  • This Question is Closed
  1. mattfeury
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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 ;)

  2. rsmith6559
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  3. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @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 :) :) :)

  4. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  5. mattfeury
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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

  6. mattfeury
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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)

  7. mattfeury
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  8. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @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
  9. mattfeury
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  10. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

    1 Attachment
  11. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  12. mattfeury
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  13. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @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....

  14. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @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
  15. mattfeury
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  16. mattfeury
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  17. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @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?

  18. mattfeury
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
  19. mattfeury
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  20. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  21. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  22. mattfeury
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  23. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  24. mattfeury
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  25. mattfeury
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  26. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  27. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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?

  28. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  29. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

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

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.