Publisher Subscriber vs Observer

July 4, 2022Uncategorizedadmin

ref –

https://blog.sessionstack.com/how-javascript-works-the-publisher-subscriber-pattern-9edc62ef1a68
https://refactoring.guru/design-patterns/observer/typescript/example
Broker Demo

The broker demo is to describe the pub/sub broker. To run it:

yarn install
yarn develop
open browser at “localhost:8080”

First, let’s take a look at the Observer Pattern.

Conceptual example on Observer Pattern

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

* The Subject interface declares a set of methods for managing subscribers.

interface Subject {

// Attach an observer to the subject.

attach(observer: Observer): void;

// Detach an observer from the subject.

detach(observer: Observer): void;

// Notify all observers about an event.

notify(): void;

}

/**

* The Subject owns some important state and notifies observers when the state

* changes.

class ConcreteSubject implements Subject {

/**

* @type {number} For the sake of simplicity, the Subject's state, essential

* to all subscribers, is stored in this variable.

public state: number;

/**

* @type {Observer[]} List of subscribers. In real life, the list of

* subscribers can be stored more comprehensively (categorized by event

* type, etc.).

private observers: Observer[] = [];

/**

* The subscription management methods.

public attach(observer: Observer): void {

const isExist = this.observers.includes(observer);

if (isExist) {

return console.log('Subject: Observer has been attached already.');

}

console.log('Subject: Attached an observer.');

this.observers.push(observer);

}

public detach(observer: Observer): void {

const observerIndex = this.observers.indexOf(observer);

if (observerIndex === -1) {

return console.log('Subject: Nonexistent observer.');

}

this.observers.splice(observerIndex, 1);

console.log('Subject: Detached an observer.');

}

/**

* Trigger an update in each subscriber.

public notify(): void {

console.log('Subject: Notifying observers...');

for (const observer of this.observers) {

observer.update(this);

}

/**

* Usually, the subscription logic is only a fraction of what a Subject can

* really do. Subjects commonly hold some important business logic, that

* triggers a notification method whenever something important is about to

* happen (or after it).

public someBusinessLogic(): void {

console.log('\nSubject: I\'m doing something important.');

this.state = Math.floor(Math.random() * (10 + 1));

console.log(`Subject: My state has just changed to: ${this.state}`);

this.notify();

}

/**

* The Observer interface declares the update method, used by subjects.

interface Observer {

// Receive update from subject.

update(subject: Subject): void;

}

/**

* Concrete Observers react to the updates issued by the Subject they had been

* attached to.

class ConcreteObserverA implements Observer {

public update(subject: Subject): void {

if (subject instanceof ConcreteSubject && subject.state < 3) {

console.log('ConcreteObserverA: Reacted to the event.');

}

class ConcreteObserverB implements Observer {

public update(subject: Subject): void {

if (subject instanceof ConcreteSubject && (subject.state === 0 || subject.state >= 2)) {

console.log('ConcreteObserverB: Reacted to the event.');

}

/**

* The client code.

const subject = new ConcreteSubject();

const observer1 = new ConcreteObserverA();

subject.attach(observer1);

const observer2 = new ConcreteObserverB();

subject.attach(observer2);

subject.someBusinessLogic();

subject.detach(observer2);

subject.someBusinessLogic();

In the observer pattern, observers are attached to a subject. When the subjects notifies them all, it calls update on the subjects. That’s how the subjects are all notified.

In other words, with the observer pattern, each observer is required to be attached to the subject, so that it can get a notification. However, the pub/sub pattern does not require this.

Difference between pub/sub and Observer

The pub/sub pattern uses a middleware that sits between the objects firing the event. In this case, the publishers and the subscribed objects.

The pub/sub pattern involves a middleware that is also referred to as the broker.

The pub/sub broker handles interactions between the publishers and the subscribers via data structures and its implementations.
Publishers publish contents or publications to the pub/sub broker and it handles the delivery of these contents to the appropriate subscriber.

The pub/sub broker also enables loose decoupling of publishers and subscribers and it supports many to many relationships between the publishers and the subscribers.

So unlike the observer pattern, the pub/sub pattern allows multiple publishers and multiple subscribers.

Example – React app that subscribes to certain topics and receives the data in the UI component

Let’s see how it is used.
In our case subscribers are clients such as a React app. In its UI component, it needs to receive data about what to change and update on certain pages.
So the React code may be like so:

subscribing on the UI

import PSBroker from "PubsubBroker";

const RacePageView: React.FC = () => (

// A React client may use our broker on its UI component to subscribe to messages.

// it gets a PSBroker object from say PSBroker npm package, subscribes to its special 'string' for events...

// and then places this line on say UI component racePageView:

PSBroker.subscription(racePageTopic, racePageViewCB).subscribe();

);

export default RacePageView;

Callback to receive published data

callback will start receiving data once an entity publishes to racePageTopic.

export const racePageViewCB = (param) => {

const [ data, type ] = param;

if (type === 'race') {

console.log(`race page view will receive data: ${data}`);

}

};

We can also use the broker in other components to subscribe to different topics to receive different data.
Again, the callback would receive the data and update the UI accordingly:

import PSBroker from "PubSubBroker";

const InvestmentPageView: React.FC = () => (

...

PSBroker.subscription(investmentViewTopic, investmentPageViewCB).subscribe();

);

export default InvestmentPageView;

callback will start receiving data once an entity publishes to investmentViewTopic.

export const investmentPageViewCB = (param) => {

const [ data, type ] = param;

if (type === 'investment') {

console.log(`investment page view will receive data: ${data}`);

}

};

The Broker

We have a Map structure that keeps track of a string key and an array of functions.
The key is the topic that different clients will subscribe to, and the array of functions keep track of the subscribers.

We use subscription to return an object that has two functionalities: subscribe and unsubscribe. It uses closure to access the needed topic name and subscriber.

When subscribe, we simply keep track of the topic name as keys in our Map, and then append subscribers (from clients) onto the value array.

class PubSubBroker {

private events: Map<string, [any]>;

constructor() {

this.events = new Map<string, [any]>();

}

subscription(topicName: string, subscriber: any) {

const subscribersArr = this.events.get(topicName);

return {

subscribe: () => {

// client subscribes to this topic

unsubscribe: () => {

// client unsubscribes

}

publish(topicName, ...args) { // publisher publishes according top topic

const subscribers = this.events.get(topicName);

// other code

}

The publishers will want to publish data according to topic name. This means all subscribers to that topic name, will receive that data.

We first to check whether we have an entry for this topic. If we do, simply push. If not, create one, then push the subscriber onto it.

const subscribersArr = this.events.get(topicName);

subscribe: () => {

if (subscribersArr) {

subscribersArr.push(func); // if it does, we simply add on the subscribers.

} else {

this.events.set(topicName, [func]);

}

console.log(`${func.name} subscribed to ${topicName}`);

}

Unsubscribe

We unsubscribe a client subscriber by iterating our values array to find it. Then remove it.

const subscribersArr = this.events.get(topicName);

unsubscribe: () => {

if (Array.isArray(subscribersArr) && subscribersArr.length > 0) {

for(let i = 0; i < subscribersArr.length; i++) {

if (subscribersArr[i].name === func.name) {

subscribersArr.splice(i, 1);

console.log(`${func.name} UnSubscribed to ${topicName}`);

return;

}

Publish

Backend apps can act as publishers and push data like so. All it needs is to know which topic it should push to.
Once we give a topic name, it’ll search for that topic, seems which subscribers are stored in the value array, and then
execute each subscriber with data as args.

publish(topicName, ...args) {

const subscribers = this.events.get(topicName);

if (Array.isArray(subscribers)) {

subscribers.forEach((subscriber) => {

subscriber.apply(null, args);

})

}

Publishers

A node server may act as a publisher. It will import PSBroker, then use it to publish data
to all the subscribers for that event topic.

import PSBroker from "../PubsubBroker";

PSBroker.publish(racePageTopic, ["Voided", "race"]);

PSBroker.publish(racePageTopic, ["Resulted", "race"]);

PSBroker.publish(investmentViewTopic, ["1024 bucks", "investment"]);

PSBroker.publish(investmentViewTopic, ["520 bucks", "investment"]);

setting up mqtt broker on mac (test with mqtt client)

June 27, 2022Uncategorizedadmin

ref –

https://medium.com/@bhagvankommadi/mosquitto-mqtt-2a352bd8f179
https://github.com/GR34SE/react-typescript-starter

React Project with MQTT client
‘yarn’ to install packages
‘yarn develop’ to run on localhost:8080

Mosquitto is an open source MQTT message broker service. It uses MQTT protocol for device to communicate by sending and receiving messages. Among the message brokers that support MQTT, Mosquitto is a small and light weight implementation of MQTT v3.1/3.1.1.

Installing Mosquitto locally on your Mac

make sure you have brew installed. brew –version

Then we install mosquitto. brew install mosquitto

Create a script where we start up mosquitto. We run it by going sh mos.sh

Create password file

create a file called say, p2.txt
enter your username:password like so:

admin/root
root/root

Then place the p2.txt file into /usr/local/etc/mosquitto

Make sure we hash it:

mosquitto_passwd -U passwordfile

Then we edit mosquitto.conf in /usr/local/etc/mosquitto

restart mosquitto and then open MQTTX app.

Setting up MQTTX

MQTT X is a cross-platform MQTT 5.0 client tool open-sourced by EMQ, designed to help develop and debug MQTT services and applications faster.

name: localhost
client ID: auto-generated
username: ‘put the username you inserted into p2.txt’
password: ‘the matching password for the username’

Press connect.

Now that we’re connected, let’s create a topic. Click on ‘New Subscription’.
Let’s type topic as “/covid/#”

By using MQTTX, we send payload for topic “/covid/….” to our local MQTT broker. It will then send to all the MQTT clients that have subscribed to “/covid/….”.

Getting local MQTT broker to work with local MQTT client

Now that our local MQTT broker is working, let’s create a MQTT client.

We start off with a very basic functional component. We create strings for our MQTT broker url, which is ws://localhost:9001. The reason why we use ws here is for web service, which is the way how MQTT clients communicate with brokers. We do this over port 9001, which is reserved for ws.

src/components/HelloWorld/index.tsx

import React from "react";

import mqtt, {MqttClient} from "mqtt/dist/mqtt";

const MQTT_TAG = "MQTT";

const brokerUrl = "ws://localhost:9001";

const un = "admin";

const pwd = "admin";

const clientId = "mqttx_12345678";

const subscribeToTopic = "/messages/morning/#";

const HelloWorld: React.FC = () => (

<h1>Basic MQTT test</h1>

<p>broker url: {brokerUrl}</p>

<p>username: {un}</p>

<p>password: {pwd}</p>

<p>topic: {subscribeToTopic}</p>

</>

);

export default HelloWorld;

step 1 – create an instance of the MQTT client make sure we are connected

1	const PushClient: PushClientType = SingletonMQTTClient();

step 2 – we subscribe

1	PushClient.subscribe([subscribeToTopic]);

Step 1 – Functionality

We create an object where we return functionality to:

subscribe
unsubscribe
terminate

So we have something like this

const SingletonMQTTClient = () => {

const subscribe = (topics: string[]) => {

}

const unsubscribe = (outDatedTopics: string[]) => {

}

const terminate = () => {

}

return {

subscribe,

unsubscribe,

terminate

};

}

Step 2 – Singleton

Note that arrow functions cannot be instantiated, only function constructors can be instantiated. So this arrow function explicitly tells the readers that we intend to work with one instance only. And that this one instance will operate on these three functions. However, if it gets called over and over, it will result in multiple instances being created. So we must implement a singleton in order to ensure we only have one instance.

We create a singleton for this instance, at the top.
We call this singleton client of type InternalClient.

Our interface InternalClient calls for property _instance, which references the mqtt client object itself.
And also getL function instance, where it uses lazy loading to check if _instance is created.
If so, we return _instance. If not, we create it using create(). This ensures a singleton.

src/components/HelloWorld/index.tsx

interface InternalClient {

_instance: MqttClient | null;

instance: MqttClient;

}

const SingletonMQTTClient = () => {

// private

const client: InternalClient = {

_instance: null,

get instance() {

if (this._instance) {

return this._instance;

}

this._instance = create();

return this._instance;

}

};

// private

const create = () => {

return initOneMqttClient();

};

}

In other words, we see that whenever another source uses client, it will try to access instance. The get function ‘instance’ lazy loads _instance. Because it is null initially, it will proceed to create a new mqtt client object.

If it already has created and point to it, then we just return _instance.

Let’s take a look at how a mqtt client object is created.

We first use import npm MQTT package. We need mqtt to execute its connect function in order to return us a client object. We import MqttClient type because that is the client object’s type.

Hence, we call connect and insert our strings as parameters.
Remember that the un and pwd are username passwords we insert into p2.txt earlier into /usr/local/etc/mosquitto

Once we get that client object we simply return it to be used.

src/components/HelloWorld/index.tsx

import mqtt, {MqttClient} from "mqtt/dist/mqtt";

...

const initOneMqttClient = (): MqttClient => {

const client = mqtt.connect(brokerUrl, {

clientId,

username: un,

password: pwd

});

return client;

};

Now run the app and make sure the returned object is valid.

// step 1 - make sure we are connected

const PushClient: PushClientType = SingletonMQTTClient();

if (PushClient) {

console.log('works');

}

MQTT event handler

So now that we have a working mqtt client object, we need to implement event handlers so that we know when we are connected, messages come in, etc.

What this means is that say another Node Server acts as a data center. It wants to inform all of us mqtt clients a ‘good morning’ message on topic “/messages/morning/#”. So any mqtt client that subscribes to /messages/morning/{wildcard} will receive it.

So our Node server sends the messages to our local MQTT broker. The MQTT broker will then relay this message to us via the ‘message’ event handler.

Let’s first do event handler for “connect”. When our mqtt client is connected to the MQTT broker, we will arrive here.

const initOneMqttClient = (): MqttClient => {

...

client.on("connect", () => {

console.log(MQTT_TAG, "connected");

});

when we receive message as explained, it will come here:

const handleIncomingMessage = (topic: string, type: string, data: any) => {

console.log("handle it!");

};

client.on("message", (topic: string, message: string, packet: any) => {

console.log("topic", topic);

console.log("message", message);

console.log("packet", packet);

handleIncomingMessage(topic, message, packet);

});

Let’s send a message from our MQTTX test client:

Now, in our event handlers, we see that first, when we start up as an app, we are connected.
Then we receive this message.

Great! So we know the messages are getting received.
But we see that the packet data come in as a stream of data via Uint8Array…where each integer represents utf-8 data.
We will use Pako to inflate the message.

1	const data = pako.inflate(message);

JSON messages sent by MQTT broker

ref – https://stackoverflow.com/questions/50000744/why-is-a-json-parsed-as-uint8array-by-mqtt-js

All MQTT message payloads are just byte arrays at the transport level. If any client library is automatically converting payloads that look like strings to strings this is most likely based on a default encoding (most likely UTF-8)

That JSON contains UTF-16 chars (“Nuages \u00e9pars d\u00e9butant dans l\u2019apr\u00e8s…”) and I would guess that the UTF-8 decoder is failing so the client library is returning the byte representation you to do your own decoding:

const handleIncomingMessage = (topic: string, message: any) => {

console.log("handle it!");

console.log("topic is", topic);

console.log("message is: ", message);

};

client.on("message", (topic: string, message: string, packet: any) => {

handleIncomingMessage(topic, JSON.parse(new TextDecoder("utf-8").decode(packet.payload)));

});

udp tcp

June 24, 2022Uncategorizedadmin

ref – https://www.lifesize.com/en/blog/tcp-vs-udp/

Transmission Control Protocol (TCP) is connection-oriented, meaning once a connection has been established, data can be transmitted in two directions.

TCP has built-in systems to check for errors and to guarantee data will be delivered in the order it was sent, making it the perfect protocol for transferring information like still images, data files, and web pages.

But while TCP is instinctively reliable, its feedback mechanisms also result in a larger overhead, translating to greater use of the available bandwidth on your network.

For example, the WebSocket protocol is an independent TCP-based protocol.

User Datagram Protocol (UDP) is a simpler, connectionless Internet protocol wherein error-checking and recovery services are not required. With UDP, there is no overhead for opening a connection, maintaining a connection, or terminating a connection; data is continuously sent to the recipient, whether or not they receive it.

Although UDP isn’t ideal for sending an email, viewing a webpage, or downloading a file, it is largely preferred for real-time communications like broadcast or multitask network transmission.

abstract vs interface

June 13, 2022Uncategorizedadmin

ref –

https://stackoverflow.com/questions/479142/when-to-use-an-interface-instead-of-an-abstract-class-and-vice-versa
http://chineseruleof8.com/code/index.php/2020/12/24/abstract-typescript/
http://chineseruleof8.com/code/index.php/2021/03/24/interfaces-in-typescript/

An abstract class can have shared state or functionality
An interface is only a promise to provide the state or functionality

An abstract class allows you to create functionality that subclasses can implement or override

We can define instance variables and accept them as input using the abstract class constructor.

abstract class Book {

private author: string;

private title: string;

constructor (author: string, title: string) {

this.author = author;

this.title = title;

}

abstract getBookType (): string; // No implementation

}

Remember that an abstract class is an abstraction, we can’t instantiate it directly. Trying anyway for demonstration purposes, we’ll notice that we get an error that looks like this:

let book = new Book ( // ❌ error TS2511: Cannot create an

'Robert Greene', // instance of an abstract class.

'The Laws of Human Nature'

);

We’ll introduce one of our specific types of Book concretions — the PDF class. We extend/inherit the abstract Book class as a new subclass to hook it up.
We can only extend one abstraction.

Even though we cannot instantiate an abstract class, we can treat it as a superclass and instantiate it by
1) extending from it
2) then call super on it in the constructor

class PDF extends Book { // Extends one abstraction

private belongsToEmail: string;

constructor (author: string, title: string, belongsToEmail: string) {

super(author, title); // Must call super on subclass to instantiate Book

this.belongsToEmail = belongsToEmail;

}

An interface only allows you to define functionality, not implement it

And whereas a class can extend only one abstract class, it can take advantage of multiple interfaces

Abstract classes should be used primarily for objects that are closely related.

interfaces are best suited for providing common functionality to unrelated classes

If you are designing small, concise bits of functionality, use interfaces.

If you are designing large functional units, use an abstract class.

If you anticipate creating multiple versions of your component, create an abstract class. Abstract classes provide a simple and easy way to version your components. By updating the base class, all inheriting classes are automatically updated with the change.

Interfaces, on the other hand, cannot be changed once created in that way. If a new version of an interface is required, you must create a whole new interface.

Binary search of an array

June 11, 2022Uncategorizedadmin

ref – https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/implementing-binary-search-of-an-array

memoize recursive functions

June 11, 2022Uncategorizedadmin

ref –

https://www.digitalocean.com/community/tutorials/js-understanding-recursion
https://medium.com/@reallygordon/implementing-memoization-in-javascript-5d140bb04166

Analysis of insertion sort

June 11, 2022Uncategorizedadmin

prerequisites:

http://chineseruleof8.com/code/index.php/2017/10/11/insertion-sort/
https://www.khanacademy.org/computing/computer-science/algorithms/insertion-sort/a/analysis-of-insertion-sort

Given

Say we’re at the last element with the number 0:

[ 2, 3, 5, 7, 11, (0) ]

In order for 0 to be sorted, it must be compared to 11. Since 11 is larger is needs to slide over 1. This goes for all elements.
Thus, every element in the array has to slide over one position to the right. Then 0 gets inserted into arr[0]…ending up with [0, 2, 3, 5, 7, 11]

If we’re inserting element n into array with k elements, we use c to denote the # of lines of code to test an element (i.e 0) against an element and slide the element over.

For example, something like this:

let i = arr.length-1;

let toInsert = 0;

while (i > 0) {

let element = arr[i-1];

if (element > toInsert) { // test

arr[i] = arr[i-1]; // slide over

}

i--;

}

then c in our case is 2 operations. But nevertheless, for implementation independent, c will simply denote the # of operations it takes to do the comparison and move the element over.

Thus, it took c * k to slide k elements over in place so that [X, 2, 3, 5, 7, 11] and finally we can insert 0 at the beginning [0, 2, 3, 5, 7, 11].

Worst case scenerio

Suppose that upon every call to insert, the value being inserted is less than every element in the subarray to its left.

Say we have [8, (5), 2, 1]

Insertion sort says, we always start index 1 (which is 5) and compare with previous element. We put 5 in a tmp variable and do a comparison, 5 < 8, so we slide over 8 over. This takes c steps and we do this 1 time. [8,8,2,1]

Then insert 5 at arr[0]

[5,8,2,1]

Then we move on to index 2, which is number 2.

[5,8,(2),1]

We do a comparison, 2 < 8, so we slide 8 over .. this is c. [5,8,8,1]

Then we compare 2 < 5, and we slide 8 over .. this is c. [5, 5, 8, 1]

Now we’re at index 0, so we simply fill it with our element 2.

[2,5,8,1]

So this is c * 2.

Then we move on to index 3, which is number 4.
We do the same comparison, and up with c * 3. Because we compare and move 1 step 3 times.

c * 1 + c * 2 + c * 3 executions.

Let’s say we start off with array [8, 7, 6 , 5, 4, 3, 2, 1]
We start at index 1 as stated by Insertion sort.

Then we work on 7. We compare and move (c) for k(1) element. So that’s c * 1. We get [7 8 6 5 4 3 2 1]
Then we work on 6. We compare and move twice for 8 and 7. So that’s c * 2. We get [6 7 8 5 4 3 2 1]
Then we work on 5. We compare and move for three times for 8 7 5. So that’s c * 3. We get [5 6 7 8 4 3 2 1]

And so on, up through the last time, when k = n-1 where n is the # of total elements.

Notice n-1. Why is that? Because we do not do compare element at index 1. We start at index 1.

Thus, what you get is:
c * 1 + c * 2 + c * 3 + c * 4 .. c * (n-1) = c(1+2+3+4…n-1)

That sum is an arithmetic series, except that it goes up to n-1, rather than n.

Arithmetic Series – Summation

Now let’s use Arithmetic series to simply and prove it.

To find the sum of the 1st n terms of an arithmetic sequence:

S = n (a initial + a of n) / 2

where n is # of terms
a initial = first term
a of n = last term

Given 5 10 15 20, let’s calculate the number of elements:

20 (last value) – 5 (first value) = 15
15 / 5 = 3
3 + 1 = 4. Add 1 to the total terms due to initial value 5.

The sum of these 4 terms are:

S = 4 (5 + 20)/2 = 2 (25) = 50
check it: 5 + 10 + 15 + 20 = 50 √

Given 2 4 6 8 10 12 14 16 18 20

S = 10 (2 + 20) / 2 = 5 (22) = 110
if you add it on the calculator, its 110 √

Say we want to go further say 2 to 222
222 – 2 = 220
220 / 2 = 110
110 + 1 = 111 Don’t forget to add 1 to 110 due to our initial value 2.
S = 111 (2 + 222)/2 = 12,432

We can also calculate term at n

A at n = initial a + (n-1)d

say we get 5 10 15 20 25

We want to figure out the 3rd term

2nd term = 5 + (2-1)(5) = 10 √
3rd term = 5 + (3-1)(5) = 15 √
5th term = 5 + (5-1)(5) = 25 √
…
…
100n term = 5 + (100-1)(5) = 500 √

The Proof

Using our formula for arithmetic series, we get that the total time spent inserting into sorted subarrays is

S = n (a initial + a of n) / 2

where # of terms n is n – 1 (remember, we don’t do the comparison for the place where we insert the value)
initial a is c * 1
last term a is c * (n – 1)

Thus, given:

c * 1 + c * 2 + c * 3 + c * 4 .. c * (n-1) =
c(1+2+3+4…n-1)

total # of terms = n-1
initial a = c*1
last term = c*(n-1)

Now we plug in everything:

S = (total # of terms) ( initial a + last term a ) / 2
S = (n-1)(c*1 + c*(n-1))/2
S = c * (n-1)(1 + n – 1) / 2
S = (c*n*(n-1)) / 2 = (cn^2)/2 – cn/2

Using O notation, we discard lower order cn/2, which leaves us (cn^2)/2
We also leave constants so we get rid of c and 1/2, which leaves us n ^ 2. Therefore, O(n^2)

Can we do it faster?

The answer is yes. Suppose we have the array [2, 3, 5, 7, 11], where the sorted subarray is the first four elements, and we’re inserting the value 11.

Upon the first comparison at index 1, we see that 3 > 2. So no need to shift. That’s c * 1.
Then we go to index 2. We see 5 > 2. So no need to shift. That’s c * 1.
This goes for 5, 7, and finally 11.

These are all constants time. Because there are n-1

This is c * (n-1), which is O(n)

So under the best case of already sorted elements, we can do O(n)

Running time of Random elements

Suppose that the array starts out in a random order. Then, on average, we’d expect that each element is less than half of the # of elements to its left. This means we expect c * (1 + 2 + 3 + … + n-1 ) / 2

The running time would be half of the worst-case running time. But in asymptotic notation, where constant coefficients don’t matter, the running time in the average case would still
be O(n^2).

Almost Sorted

What if you knew that the array was “almost sorted”: every element starts out at most some constant number of positions, say 17, from where it’s supposed to be when sorted? Then each call to insert slides at most 17 elements, and the time for one call of insert on a subarray of k elements would be at most c * 17.

Over all n-1 calls to insert, the running time would be at most 17 * c * (n-1).

which is O(n) just like the best case. So insertion sort is fast when given an almost-sorted array.

Auxiliary Space

June 4, 2022Uncategorizedadmin

ref – https://www.geeksforgeeks.org/g-fact-86/#:~:text=Auxiliary%20Space%20is%20the%20extra,and%20space%20used%20by%20input.

Auxiliary Space is the extra space or temporary space used by an algorithm.

Space Complexity of an algorithm is the total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input

Hence, Auxiliary Space is a subset of Space Complexity.

js vs typescript

May 22, 2022Uncategorizedadmin

ref – https://tsh.io/blog/typescript-vs-javascript-comparison/

java instances + mac

May 13, 2022Uncategorizedadmin

ref – https://www.delftstack.com/howto/java/change-java-version-mac/

To see what version of Java you have installed:

/usr/libexec/java_home -V

1.8.45.14 (x86_64) “Oracle Corporation” – “Java” /Library/Internet Plug-Ins/JavaAppletPlugin.plugin/Contents/Home
1.8.0_45 (x86_64) “Oracle Corporation” – “Java SE 8” /Library/Java/JavaVirtualMachines/jdk1.8.0_45.jdk/Contents/Home

In my case, when I decided to install an older version of JDK (jdk-8u45-macosx-x64), it installed at

java -version (note one dash)

java version “1.8.0_45”
Java(TM) SE Runtime Environment (build 1.8.0_45-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.45-b02, mixed mode)

So I’m using 1.8.0

Sometimes, it installs in other locations: