Arrays:

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).

Array Representation

Arrays can be declared in various ways in different languages. For illustration, let’s take C array declaration.

Arrays can be declared in various ways in different languages. For illustration, let’s take C array declaration.

As per the above illustration, following are the important points to be considered.

• Index starts with 0.
• Array length is 10 which means it can store 10 elements.
• Each element can be accessed via its index. For example, we can fetch an element at index 6 as 9.

Basic Operations

Following are the basic operations supported by an array.

• Traverse− print all the array elements one by one.
• Insertion− Adds an element at the given index.

Insertion Operation

Insert operation is to insert one or more data elements into an array. Based on the requirement, a new element can be added at the beginning, end, or any given index of array.

Here, we see a practical implementation of insertion operation, where we add data at the end of the array −

Let LA be a Linear Array (unordered) with N elements and K is a positive integer such that K<=N. Following is the algorithm where ITEM is inserted into the K^th position of LA −

1. Start
2. Set J = N
3. Set N = N+1
4. Repeat steps 5 and 6 while J >= K
5. Set LA[J+1] = LA[J]
6. Set J = J-1
7. Set LA[K] = ITEM
8. Stop

• Deletion− Deletes an element at the given index.
• Search− Searches an element using the given index or by the value.
• Update− Updates an element at the given index.

Python Arrays

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).

Python program to demonstrate 

Some of the data types are mentioned below which will help in creating an array of different data types.

Adding Elements to a Array

Insert is used to insert one or more data elements into an array. Based on the requirement, a new element can be added at the beginning, end, or any given index of array.append() is also used to add the value mentioned in its arguments at the end of the array.

Python program to demonstrate

# Adding Elements to a Array

Accessing elements from the Array

In order to access the array items refer to the index number. Use the index operator [] to access an item in a array. The index must be an integer.

Access element is:  10Access element is:  44Access element is:  7.2Access element is:  9.3

Removing Elements from the Array:

Elements can be removed from the array by using built-in remove() function but an Error arises if element doesn’t exist in the set. remove() method only removes one element at a time, to remove range of elements, iterator is used. pop() function can also be used to remove and return an element from the array, but by default it removes only the last element of the array, to remove element from a specific position of the array, index of the element is passed as an argument to the pop() method.

# Python program to demonstrate

# Removal of elements in a Array

 Slicing of a Array:

Slice operation is performed on array with the use of colon(:). To print elements from beginning to a range use [:Index], to print elements from end use [:-Index], to print elements from specific Index till the end use [Index:], to print elements within a range, use [Start Index: End Index] and to print whole List with the use of slicing operation, use [:]. Further, to print whole array in reverse order, use [::-1].

Searching element in a Array

In order to search an element in the array we use a python in-built index() method. This function returns the index of the first occurrence of value mentioned in arguments.

Updating Elements in a Array

Python code to demonstrate

# how to update an element in array

# importing array module

import array

 

# initializing array with array values

# initializes array with signed integers

arr = array.array(‘i’, [1, 2, 3, 1, 2, 5])

 

# printing original array

print (“Array before updation : “, end =””)

for i in range (0, 6):

print (arr[i], end =” “)

 

print (“\r”)

 

# updating a element in a array

arr[2] = 6

print(“Array after updation : “, end =””)

for i in range (0, 6):

print (arr[i], end =” “)

print()

 

# updating a element in a array

arr[4] = 8

print(“Array after updation : “, end =””)

for i in range (0, 6):

print (arr[i], end =” “)

 

Output:

Array before updation : 1 2 3 1 2 5 Array after updation : 1 2 6 1 2 5 Array after updation : 1 2 6 1 8 5

 

Split the array and add the first part to the end

There is a given an array and split it from a specified position, and move the first part of array add to the end.

 

Input : arr[] = {12, 10, 5, 6, 52, 36}            k = 2Output : arr[] = {5, 6, 52, 36, 12, 10}Explanation : Split from index 2 and first part {12, 10} add to the end . Input : arr[] = {3, 1, 2}           k = 1Output : arr[] = {1, 2, 3}Explanation : Split from index 1 and firstpart add to the end.

 

#Python program to split array and move first

# part to end.

 

def splitArr(arr, n, k):

for i in range(0, k):

x = myarray[0]

for j in range(0, n-1):

myarray [j] = myarray [j + 1]

 

myarray [n-1] = x

 

# main

myarray = [12, 10, 5, 6, 52, 36]

n = len(myarray)

position = 2

 

splitArr(myarray, n, position)

 

for i in range(0, n):

print(myarray [i], end = ‘ ‘)

Output:

5 6 52 36 12 10

 

Program for array rotation

leftRotate(arr[], d, n)start  For i = 0 to i < d    Left rotate all elements of arr[] by oneend

To rotate by one, store arr[0] in a temporary variable temp, move arr[1] to arr[0], arr[2] to arr[1] …and finally temp to arr[n-1]

Let us take the same example arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2
Rotate arr[] by one 2 times
We get [2, 3, 4, 5, 6, 7, 1] after first rotation and [ 3, 4, 5, 6, 7, 1, 2] after second rotation.

Below is the implementation of the above approach :

# Python3 program to rotate an array by d elements

# Function to left rotate arr[] of size n by d*/

def leftRotate(arr, d, n):

for i in range(d):

leftRotatebyOne(arr, n)

 

# Function to left Rotate arr[] of size n by 1*/

def leftRotatebyOne(arr, n):

temp = arr[0]

for i in range(n-1):

arr[i] = arr[i + 1]

arr[n-1] = temp

 

# utility function to print an array */

def printArray(arr, size):

for i in range(size):

print (“% d”% arr[i], end =” “)

 

# Driver program to test above functions */

arr = [1, 2, 3, 4, 5, 6, 7]

leftRotate(arr, 2, 7)

printArray(arr, 7)

 

Output :

3 4 5 6 7 1 2

Time complexity : O(n * d)
Auxiliary Space : O(1)

 

For the input of size n, an algorithm of O(n) will perform steps perportional to n, while another algorithm of O(log(n)) will perform steps roughly log(n).

Clearly log(n) is smaller than n hence algorithm of complexity O(log(n)) is better. Since it will be much faster.

Generally, when referring to big O notation, log n refers to the base-2 logarithm, (same way lnrepresents base e logarithms). This base-2 logarithm is the inverse of an exponential function. An exponential function grows very rapidly and we can intuitively deduce that it’s inverse will do the exact opposite i.e grows very slowly.

For example

x = O(log n)

We can represent n as ,

n= 2^x

And

2¹⁰ = 1024 → lg(1024) = 10

2²⁰ = 1,048,576 → lg(1048576) = 20

2³⁰ = 1,073,741,824 → lg(1073741824) = 30

Large increments in n only lead to a very small increase in log(n)

For a complexity of O(n) on the other hand, we get a linear relationship

A factor of log₂n should be taken over A factor of n anytime.

To further solidify this, I came across an example in Algorithms Unlocked By Thomas Cormen

Consider 2 computers : A and B

Both Computers have a task of searching an array for a value Let’s assume the arrays have 10 million elements to be searched through

Computer A- This computer can execute 1 billion instructions per second and is expected to perform the above task using an algorithm with a complexity of O(n). We can approximate the time is takes this computer to complete the task as

n/(instructions p second) → 10⁷/10^9 = 0.01 seconds

Computer B- This computer is much more slower, and can execute only 10 million instructions per second. Computer B is expected to perform the above task using an algorithm with a complexity of O(log n). We can approximate the time is takes this computer to complete the task as

log(n) /(instructions p second) → log(10⁷)/10⁷ = 0.000002325349

With this illustration, we can see that even though computer A is much better than computer B,due to the algorithm used by B, it completes the task much quicker.

I think it should be very clear now why O(log(n)) is much faster than O(n)