The cost of amortized time complexity

ahmedmenaem — Sat, 09 May 2020 23:48:29 +0000

Amortized Time Complexity, worst case happens every once in a while.

I'm so tired of searching for good resources that discussing amortized time complexity, so what is the meaning of amortized time?

first thing let's define the meaning for the array, and why we need it?

Array

In computer science, an array data structure or simply an array is a data structure that consisting of a collection of elements values or variables.

let's simplify it, an array is a data structure that can contain multiple values, we can think of it as a list of multiple things.

an array is a contiguous block of memory, let's imagine that we have an array of size 5, so it will reserve 5 blocks (block after block) in the memory, so memory will always have a fixed size.

How programming languages solve the fixed-size problem to give us the ability to create a dynamical size array.

Many programming languages solve this problem by creating an ArrayList or Dynamically resizing array.

What is array list?

is a data structure that allows us to have the benefits of an array while offering flexibility in size, you won't run out of space since in the Array List will grow as you insert elements.

The Array List is implemented with an array as the hurt of its logic when the array hits capacity, the Array List will create a new array with double the capacity and copy all the elements over the new area.

Whaaaaaat, what did you said ??

Yeh, it is doing 2 operations:

create a new array with double size of the old one.
copy all elements over to the new array.

as we know that when we insert new value at the end of the array, it is required a single operation with constant time complexity O(1), Please check this link, if you don't know, how to describe your runtime Big O noation

So, What is the runtime (complexity) of the insertion?

let's explain how it works?, the array could be full, if the array contains N elements then inserting new element will take O(n) time because we have to create a new array of size 2*N and then copy N elements over the new array.

we know that it doesn't happen very often, the vast majority of the time insertion will be O(1).

So, what is amortized time does?

Amortized time allows us to describe these cases, cases that happen every once in a while, and won't happen again for a while.

In case that we discussed, the amortized time is:

when we insert a new element, the first thing we are going to double the array capacity the double-takes respectively 1, 2, 4, 8, 16, 32, 64, X, so what we mean by the sum of this equation? this is roughly 2X.

Therefore, X insertion takes O(2X). the amortized time for each insertion is O(1), so we are not saying it O(1) time complexity, it is amortized O(1) time complexity.

Summary

Amortized time describes cases that happen every once in a while, and won't happen again for a while.

resources

Reactive programming for lazy programmers.

ahmedmenaem — Sun, 03 May 2020 11:13:29 +0000

Introduction to Reactive programming for lazy programmers.

I know you are tired and exhausted from searching for a good introduction about reactive programming, you listened for a lot of people but finally, you find this series.

In this series, I'm going to give you the bedrock of reactive programming,
let's dive together and learn what we need.

What is Reactive Programming?

There are plenty of bad explanations and definitions about reactive programming, so let's cut it in a little definition.

Reactive Programming

is programming with asynchronous data streams.

Oh Whaaaaaat ???

come down, this isn't anything new, event buses or typical click events are really an asynchronous event stream which you can observe and do some side effects, so what is the reactive programming main idea? reactive programming gives you the ability to create data streams of anything.

Streams: are cheap and ubiquitous, anything can be a stream, variables, user inputs, properties, caches, data structure, etc..

Stream

a stream is a sequence of ongoing events ordered in time,
it can emit 3 different things:

value (of some type)
error (something wrong happened)
completed signal (when the stream is done or completed) we captured these emitted events only asynchronously, by defining a function that will execute when a value is emitted, another function when an error is emitted and another function when completed is emitted, sometimes we can omit the last 2 functions and we can just focus on defining the function for values.

The listening to the stream is called subscribing. by subscribing to an
observable you are going listen to any new change

Observer

The functions that we are defining to deal with the ongoing events are called observers, it contains 3 functions (next, error, complete).
It is an object usually given to the observable.subscribe(observer), Observable will call the Observer's next(value) method to provide notifications, a well-behaved Observable will call an Observer's complete() method exactly once or the Observer's error(err) method exactly once, as the last notification delivered.

Subject

Observable or subject is what is observed by observers.
we can imagine it as a data store that will send a notification whenever change happened to its value.

Oh that's the Observer Design Pattern, so please check it

What is the difference between Promise and Observable?

There is no big difference, both are promising us with a value in the future when some event happens, but the main difference between them that Promise will emit a single value, on the other side Observable returned many values over time.

Why should I consider adopting Reactive Programming?

Reactive programming raises the level of abstraction of our code, so we can focus on the interdependence of events that define the business logic, rather than having to constantly fiddle with a large amount of implementation details. Code in Reactive Programming will likely be more concise

Benefits of using Reactive Programming

The benefits are more evident in modern web apps and mobile apps that are highly interactive with a multitude of UI related to data events, for example, "likes" on Facebook can be reflected in realtime to other connected users.

Summary

Reactive programming is really suitable for real-time web apps and mobile applications, it is really helpful when we are dealing with multiple components dealing with the same data source and interested in data change.

That's a simple intro about reactive programming and in the next article, we are going to talk about how to implement it using RXJS the reactive extension for javascript.

DEV Community: ahmedmenaem

The cost of amortized time complexity

Amortized Time Complexity, worst case happens every once in a while.

Array

How programming languages solve the fixed-size problem to give us the ability to create a dynamical size array.

What is array list?

Whaaaaaat, what did you said ??

So, What is the runtime (complexity) of the insertion?

we know that it doesn't happen very often, the vast majority of the time insertion will be O(1).

So, what is amortized time does?

Summary

resources

Reactive programming for lazy programmers.

Introduction to Reactive programming for lazy programmers.

What is Reactive Programming?

Reactive Programming

Oh Whaaaaaat ???

Stream

Subscribe

Observer

Subject

Oh that's the Observer Design Pattern, so please check it

What is the difference between Promise and Observable?

Why should I consider adopting Reactive Programming?

Benefits of using Reactive Programming

Summary

Links

Please check this links and your feedback is really matter