Win a copy of Cross-Platform Desktop Applications: Using Node, Electron, and NW.js this week in the JavaScript forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Is it nlogn or logn ?  RSS feed

 
naved momin
Ranch Hand
Posts: 692
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi all,

Just a simple question, suppose i have given a I am iterating over list and inserting each element from list into BST, if time require to insert into BST is logn then what is the total time require to insert all the elements into tree ?

logn or nlogn ?
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
naved momin wrote:JI am iterating over list and inserting each element from list into BST, if time require to insert into BST is logn then what is the total time require to insert all the elements into tree ?
logn or nlogn ?

What do you think Naved? C'mon, this isn't rocket science...

Also: Please don't use abbreviations like BST without explaining at least once what you mean by them. TLA's are the bane of our profession.

Winston

[Edit] For the benefit of others, I probably should have said that "BST" is (probably) short for "binary search tree", which I would assume to be similar to a TreeMap (or Set).
 
naved momin
Ranch Hand
Posts: 692
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
According to me its nlogn, what you think ?
 
Paul Clapham
Sheriff
Posts: 22374
42
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It obviously can't be O(log n) because just examining each of n objects is O(n), which is larger. So O(n log n) sounds more likely to me except that your statement "time require to insert into BST is logn" presumably refers to inserting into a BST (whatever that is) which already has n entries in it.
 
Jayesh A Lalwani
Rancher
Posts: 2762
32
Eclipse IDE Spring Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah, actually it's sum(log(x)) for x = 1 to n which comes out to log(n!) which approximates to n log(n). SO, it's n log n
 
fred rosenberger
lowercase baba
Bartender
Posts: 12527
48
Chrome Java Linux
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote: TLA's are the bane of our profession.

TLA = Three Letter Acronym.

And my personal favorite:
XTLA - eXtended Three Letter Acronyms.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!