Tight upper bound for forming an $n$ element Red-Black Tree from scratch

I learnt that in a order-statistic tree (augmented Red-Black Tree, in which each node $ x$ contains an extra field denoting the number of nodes in the sub-tree rooted at $ x$ ) finding the $ i$ th order statistics can be done in $ O(lg(n))$ time in the worst case. Now in case of an array representing the dynamic set of elements finding the $ i$ th order statistic can be achieved in the $ O(n)$ time in the worst case.[ where $ n$ is the number of elements].

Now I felt like finding a tight upper bound for forming an $ n$ element Red-Black Tree so that I could comment about which alternative is better : "maintain the set elements in an array and perform query in $ O(n)$ time" or "maintaining the elements in a Red-Black Tree (formation of which takes $ O(f(n))$ time say) and then perform query in $ O(lg(n))$ time".


So a very rough analysis is as follows, inserting an element into an $ n$ element Red-Black Tree takes $ O(lg(n))$ time and there are $ n$ elements to insert , so it takes $ O(nlg(n))$ time. Now this analysis is quite loose as when there are only few elements in the Red-Black tree the height is quite less and so is the time to insert in the tree.

I tried to attempt a detailed analysis as follows (but failed however):

Let while trying to insert the $ j=i+1$ th element the height of the tree is atmost $ 2.lg(i+1)+1$ . For an appropriate $ c$ , the total running time,

$ $ T(n)\leq \sum_{j=1}^{n}c.(2.lg(i+1)+1)$ $

$ $ =c.\sum_{i=0}^{n-1}(2.lg(i+1)+1)$ $

$ $ =c.\left[\sum_{i=0}^{n-1}2.lg(i+1)+\sum_{i=0}^{n-1}1\right]$ $

$ $ =2c\sum_{i=0}^{n-1}lg(i+1)+cn\tag1$ $

Now

$ $ \sum_{i=0}^{n-1}lg(i+1)=lg(1)+lg(2)+lg(3)+…+lg(n)=lg(1.2.3….n)\tag2$ $

Now $ $ \prod_{k=1}^{n}k\leq n^n, \text{which is a very loose upper bound}\tag 3$ $

Using $ (3)$ in $ (2)$ and substituting the result in $ (1)$ we have $ T(n)=O(nlg(n))$ which is the same as the rough analysis…

Can I do anything better than $ (3)$ ?


All the nodes referred to are the internal nodes in the Red-Black Tree.

Forming groups of people such that no group has two people that dislike each other

I had an assignment for the graph theory unit of my data structures course. The problem was given as follows:

Every person in a class has at least one other person that they dislike and will not work with. Form groups so that everyone gets along with their group members. You are not allowed to form more than $ k$ groups in total. Given a list of pairs of people who dislike each other, and the number $ k$ , return a grouping of students if it is possible, otherwise return None.

I have found a way to generalize this problem more succinctly if it helps:

Given a binary relation $ R$ on a set $ S$ , find an equivalence relation $ R’$ on the set $ S$ such that $ R \cap R’=\emptyset$ and the size of the quotient set of $ S$ by $ R’$ less than $ k$ .

My attempt was to solve the problem using a DFS on the tree of partitions of $ S$ . Start with an empty partition then try to insert some person, forming a new “vertex” of the tree. Continue doing this until a leaf is reached, or a state that has already been visited is seen. The problem with this solution is that although it is correct, it is too slow. Cases with 8 groupings can take several minutes to find, and the list of visited states becomes so massive that the program runs out of memory.

def enemyDicc(dislikes):     result = {}     for x, y in dislikes:         if x in result:             result[x].add(y)         else:             result[x] = {y}          if y in result:             result[y].add(x)         else:             result[y] = {x}     return result   def formGroups(dislikes, max_):     enemiesOf = enemyDicc(dislikes)     ppl = list(enemiesOf.keys())     failed = []      def findFrom(people, grouping):         # dont make the same mistakes         if grouping in failed:             return None         if len(grouping) == len(ppl):             # everyone is in this grouping and we are done             return grouping         grp_ids = set(grouping.values())         # extra param for edge case at start         num_grps = max(grp_ids, default=0)         for i, person in enumerate(people):             # find a group that can take this person             found = False             for id_ in grp_ids:                 hater_in_grp = any(enemy in grouping and grouping[enemy] == id_                                    for enemy in enemiesOf[person])                 if not hater_in_grp:                     grouping[person] = id_                     found = True             # if no one can, try to make a new one             if num_grps < max_:                 grouping[person] = num_grps + 1                 found = True             # if not possible move on to next person             if found:                 # try to build from this grouping                 # without the person                 nxt_grp = findFrom(people[:i]+people[i+1:], grouping)                 # if a valid grouping is found return it                 if nxt_grp:                     return nxt_grp                 else:                     # otherwise delete the person from the grouping                     del grouping[person]                     # move on to the next person         # if this point is reached there is no valid grouping         failed.append(dict(grouping))         print(len(failed))         return None      return findFrom(ppl, {}) 

Forming Date time using LocalDateTime with zone

I am trying to get the date formate using LocalDateTime and Country Code

I tried with ZonedDateTime and ZoneId

        final String inputDateStr = "20181227";         String inputHourStr = "1030";         LocalDateTime approvalDateTime = LocalDateTime.of(Integer.parseInt(inputDateStr.substring(0, 4)), Integer.parseInt(inputDateStr.substring(4, 6)),              Integer.parseInt(inputDateStr.substring(6, 8)), Integer.parseInt(inputHourStr.substring(0, 2)), Integer.parseInt(inputHourStr.substring(2, 4)));          ZoneId zoneId = ZoneId.of("Europe/Paris");         ZonedDateTime zonedApprovedDateTime = ZonedDateTime.of(approvalDateTime, zoneId);         String zonedApprovedDateTimeStr = zonedApprovedDateTime.toString();         System.out.println(zonedApprovedDateTimeStr);  

I have object of LocalDateTime ( LocalDateTime approvalDateTime = //).

String approvalDateTimeStr = approvalDateTime.toString(); System.out.println(approvalDateTimeStr); // which prints 2018-12-27T10:30

I need to get the value like this 2018-12-27T10:30+08:00 based on country code(SG,MY). I have two input one is LocalDateTime object and another one is country code

I tried with ZonedDateTime and ZoneId, but it is printing (2018-12-27T10:30+01:00[Europe/Paris]). The country code is dynamic.

ZoneId zoneId = ZoneId.of(“Europe/Paris”); ZonedDateTime zonedApprovedDateTime = ZonedDateTime.of(approvalDateTime, zoneId);

Ramda – Forming a string based on array of word positions

I saw this question and wondered how it’d be best to accomplish this using Ramda.

I’m new to the library so I thought it’d be an interesting learning exercise.

I have a working solution but it seems overly complicated and verbose. I’d be grateful for any suggestions on what other ways it would be possible to achieve this output using Ramda.

I’m aware that this doesn’t need a library; as I say, I approached it as a learning exercise.

Here’s what I have:

const { addIndex, always, fromPairs, join, map, sort, toPairs, unnest } = R;  const song = {   "99": [0, 7],   "bottles": [1, 8],   "of": [2, 9],   "beer": [3, 10],   "on": [4],   "the": [5],   "wall": [6] };  const toSentence = join(' ');  const parsed = toSentence(     map(       ([_, word]) => word,       sort(         ([a, _], [b, __]) => a < b ? -1 : 1,         unnest(map(           ([word, indices]) => map(             index => [index, word],             indices,           ),           toPairs(song)         ))       )     )   )    console.dir(parsed)
<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.26.1/ramda.js"></script>

pen forming yeah warriors disappear activate

5, or 10 kilometers to earn awards, according to Dr. http://www.olivehomestudio.com/olivehome/event/389927 read all bollocks surface india drugstore online cuff otc vitamins for anxiety https://www.foro.desterium.com/viewtopic.php?f=9&t=148909 https://wiki.hvacrealm.com/index.php?title=Mai_Locks_Yards_Insane chili martyr http://cosmeticsocial.net/groups/buy-usa-crestor-buy-crestor-oklahoma-city-usage/…

pen forming yeah warriors disappear activate

forming recurrence equations from code

Please could someone help me with understanding how to form recurrence equations when reading code? I’m having some trouble in my class:

 public Map<K, V> combine(ArrayList<Map<K, V>> list) {     Map<K, V> result = new HashMap<>();     if (list != null && list.size() > 0) {       combineHelper(list, 0, list.size() - 1, result);     }     return result;   }        private void combineHelper(ArrayList<Map<K, V>> list, int i, int k, Map<K, V> result) {         if (i == k) {           result.putAll(list.get(i));           return;         }      int mid = i + (k - i) / 2;     combineHelper(list, i, mid, result);     combineHelper(list, mid + 1, k, result); 

It says that i’m supposed to write the recurrence equation for this and explain it. But I’m not really sure how I’m supposed to do that.

They’ve given this hint Define n=k−i+1, but i’m still stuck. Much help would be appreciated.

Thanks