Time complexity of various operations in python list

Time complexity is the amount of time required to execute the program . Time complexity  is calculated using “Big O”

Here i give a description of amount of time take each opeartions in python data types. Let us take input size as “n” and “m’ is additional parameter

List

A list in python is like array contain a sequence . Below a description about time complexity of varous list operations. Individual actions (append etc.) in any operation take  time complexity is O(1) else depend on size of input because after some operation elements must move their positions and time will vary (insert , extend etc.)

append       –  O(1)       insert element at end of list , no moving

insert             – O(n)    inserting begining or at a position , so elements move to right n times

delete item     – O(n)    elements move after deleted positon depend upon size of input

iteration        – O(n)    iterating n times

get slice        –  O(k)    k a value of parameter

extend          –  O(k)    k is new list to extend

get item        –  O(1)

set item        –  O(1)

get length     –  O(1)

i in list         –  O(n)

sort              –  O(n logn)

Optimization strategy of fibonacci series

Fibnoacci series is a basic example which teach recursion . Recursion a powerful programming  paradigm in which a function call itself .

Here a simple program of fibonacci series using recursion

def f(n):
 if n < 2:
   return n
 return  f(n-1) + f(n-2)

But this program just getting f(40) take atleast 8 minutes and for f(50) take really a long time , so it  is less efficient and too slow

why it slow?

The short answer is ‘recursion’ . Let us see how many times fibnocci function  calls itself recursively to compute f(50)

• f(50) is called once
• f(49) is called once
• f(48) is called 2 times
• f(47) is called 3 times
• f(46) is called 5 times
• f(45) is called 8 times
• …..
• f(1) is calculated 12,586,269,025 times

Number of recursively call grows  high rate , this simple program take O(2^n) times.

The main problem is that there is no way of remembering already calulated values . So it recalculate the same again, this recalculation take a larger time and then efficiency decreses and if number of input larger then duplicate calculation increses., and result take more time, therfore  we need a optimization strategy

Memoization

Memoization is a optimization strategy  which store the results for  later use and no recalculation

Below program explain how memoizing in fibonacci series

cache = {}
def fib(n):
  if n in cache:
     return cache[n]
  else:
     if n <2:
       cache[n]=n
     else:
      cache[n]= fib(n-1) + fib(n-2)
     return cache[n]

Here the dictionary named cache store the numbers which already calculated. When fibnocci function is called it check the cache if it contain result, if contain then function return immediately and no more recursive calls. If not ,  it has to compute new value and this value added to cache.

so using memoization there is no recalculation and we got result faster for large numbers. This test take less than one second please try it ….and see how faster it..

Basics of python

Python a scripting language with simple syntax and does not need compilation.  Its codes are too short and flexible, i interested to learn python because it easy to learn and simple.  Due to its open source nature python is portable also we run the program directly from the source code.

In my laptop python version 2.6.4 already installed and i started to programming in python ,this my first step to  world of python

just type python on terminal and then enter,

$ python
Python 2.6.4 (r264:75706, Oct 29 2009, 15:38:25)
[GCC 4.4.1] on linux2
Type “help”, “copyright”, “credits” or “license” for more information.
>>> print ‘Hello world’
Hello world
>>>

Python gives you the output of the line immediately! What you just entered is a single Python statement. We use print to  print any value that you supply to it. Here, we are supplying the text Hello world and this is promptly printed to the screen.

python  as a simple calculator

We can type any expression in interpreter and it will write value, operators +, -, * and / work just like in most other languages

>>> 2+2
4
>>> 2-2
0
>>> 2//2
1
>>> 2/2
1b
>>> (50-5*6)/4
5
>>> 7/-3
-3
>>>

Different python datatypes

    Strings

  Strings in python is a series of  characters . Strings surrounded by   ”  ”  or   ‘  ‘

  Strings are immutable

  >>> flower=”Rose”
  >>> print flower
  Rose
 >>> len(flower)
 4
 

String slices   –  Substring of a string called slice

>>> fruit=”banana”
>>> fruit[:3]
‘ban’
>>> fruit[3:]
‘ana’
>>> fruit[2:]
‘nana’

The operator [n:m] returns the part of the string from the n-th character to the m-eth character, including the first but excluding the last.

Lists

Lists are ordered set of values defined with index

>>> list=[1,2,3,4,5]
>>> list
[1, 2, 3, 4, 5]
>>>
Common list operations

• list.append(elem) — adds a single element to the end of the list.
• list.insert(index, elem) — inserts the element at the given index, shifting elements to the right.
• list.extend(list2) -adds the elements in list2 to the end of the list. Using + or += on a list is similar to using extend().
• list.index(elem) — searches for the given element from the start of the list and return index               
• list.remove(elem) — searches for the first instance of the given element and removes it
• list.sort() — sorts the list in place (does not return it). (The sorted() function shown below is preferred.)
• list.reverse() — reverses the list in place (does not return it)
• list.pop(index) — removes and returns the element at the given index. Returns the rightmost element if index is omitted (roughly the opposite of append()).

Dictionary

Python built-in  mapping type. Map keys to values

>>> dict={}
>>> dict[‘a’]=1
>>> dict[‘b’]=2
>>> dict[‘c’]=3
>>> dict
{‘a’: 1, ‘c’: 3, ‘b’: 2}
>>>

File

• To open a file  –   file=open(filename, mode)
•  To read a file  –    file.read()
•  To write to file  – file.write()
• To close a file  –  file.close()                   
  

Regular expressions  –     

Regular expressino is for pattern matching in a text file. ‘re ‘ module provide all functions for regular expressions .

• re.search(pat, text)  – Search a pattern in given text
• match.group() – Return the pattern
• re.findall() – All instances match this expression
• re.sub(paten,  replace, str)  – Search  all instances of given pattern in string and replace

Python utilities      Python provide many utility modules

os module - os module include functions to interact with filesystem

• filenames = os.listdir(dir)  – list of filenames in directory  ‘dir’
• os.path.join(dir,  filename)  – path of filename in directory
• os.path.abspath(path)  – given a path ,return absolute form
• os.path.dirname(path)  – give as dir/foo/bar.html
• os.path.basename(path) – give basename as bar.html
• os.path.exists()   – true if exists
• os.mkdir(dir) – make a directory
• shutil.copy(sourcepath, destpath)  –  copy files from source to destination

 commands module - Run external commands and capture output

• (status, output) = commands.getstatusoutput(cmd) – run command and return status and output.  if status is nonzero command failed
• commands.getstatus()  –  give status
• commands.getoutput()  – return value is a string containing output

urllib module - provide url fetch

• ufile = urllib.urlopen(url) -return file for given url
• text=ufile.read() – read like a file
• info = ufile.info() — the meta info for that request
• baseurl = ufile.geturl() — gets the “base” url for the request
• urllib.urlretrieve(url, filename) — downloads the url data to the given file path
• urlparse.urljoin(baseurl, url) — given a url that may or may not be full, and the baseurl of the page come and return full url