Posts

Intuition for O(log 𝑛) time complexity of the update and query operations in a Segment tree

Image
I had posted an answer to similar question 5 years ago on quora . Reposting the same here. Time complexity for query operations in a segment tree is O(log n) because there are O (log n) levels in a segment tree and at max we will have to process 4 nodes in a level. Let’s go through some pictures depicting a few arrangements which should give an idea why at max only 4 nodes are processed in a level. We should keep in mind that the query is always for a continuous range. First let us see some arrangements when we will have to process (or not process) 4 nodes in a level through some pictures. Black nodes are totally overlapped nodes, half black nodes are partially overlapped nodes and white nodes of last level are the ones which are not at all in the query interval. Case 1: The above arrangement is not possible to have. Why ? As the query is for continuous range, we can not have a ‘not included’ node in between. Case 2: Even this arrangement is not possible because for this arrangement ...
Post a Comment
Read more

END-TO-END ARGUMENTS IN SYSTEM DESIGN

END-TO-END ARGUMENTS IN SYSTEM DESIGN paper is one of the classic papers written by J.H. Saltzer, D.P. Reed and D.D. Clark. This paper discusses one of the design principles, called end-to-end argument , which provides guidance about where to place a function in layered systems. The paper argues that function implementation should be moved upward in layered systems - closer to the application that uses the function. Paper examines the end-to-end argument in detail using reliable data transmission in a communication system. "The function in question can completely and correctly be implemented only with the knowledge and help of the application standing at the end points of the communication system. Therefore, providing that questioned function as a feature of the communication system itself is not possible. (Sometimes an incomplete version of the function provided by the communication system may be useful as a performance enhancement.)." This paper examines the end-to-end ar...
Post a Comment
Read more