Win a copy of Cross-Platform Desktop Applications: Using Node, Electron, and NW.js this week in the JavaScript forum!
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Is it nlogn or logn ?

naved momin
Ranch Hand
Posts: 692
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
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

 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
According to me its nlogn, what you think ?

Paul Clapham
Sheriff
Posts: 22374
42
• 1
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
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
• 2
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.