Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Time complexity of algorithms
 Data structures are ways of organizing data for efficiently accessing and manipulating
them
...

 Algorithms are procedures for solving problems
...
It is denoted as T(n), where n is the input size
...
Big O notation describes
the asymptotic behavior of an algorithm, which means how the algorithm's running time
changes as the input size gets larger and larger
...

For example, the following algorithm has constant time complexity:

def constant_time_algorithm(n):
return n + 1

 Linear time complexity (O(n)): The algorithm's running time is proportional to the size
of the input n
...


For example, the following algorithm has exponential time complexity:

def exponential_time_algorithm(n):
if n == 0:
return 1
else:
return 2 * exponential_time_algorithm(n - 1)

Other types of complexities are :







Logarithmic time complexity (O(log n))
Quasilinear time complexity (O(n log n))
Subquadratic time complexity (O(n^a), where a < 2)
Cubic time complexity (O(n^3))
Exponential time complexity (O(2^n))
Factorial time complexity (O(n!))

BONUS
Time complexity (T(n)) for commonly used data structures are :
Arrays
 Access: O(1)
 Insertion: O(n)
 Deletion: O(n)
Linked Lists
 Access: O(n)
 Insertion: O(1)
 Deletion: O(1)
Stacks
 Push: O(1)
 Pop: O(1)
 Peek: O(1)

Queues
 Enqueue: O(1)
 Dequeue: O(1)
 Peek: O(1)
Trees
 Search: O(log n)
 Insertion: O(log n)
 Deletion: O(log n)
Graphs
 Search: O(n)
 Traversal: O(n)
 Shortest path: O(n^2)



---