Data Structures and Algorithms — scratching the surface

NumArray = [1, 2, 3, 4, 5]
// access element at index 2
elem = NumArray[2]// elem is 3
  • Preorder traversal
  • Postorder traversal
  • Inorder traversal
  • Kruskal’s Algorithm
  • Prim’s Algorithm

Asymptotic notations are mathematical tools for representing performance of algorithm in terms of time complexity.

Arr = [4, 3, 2, 7, 8]// time complexity to find 4 in the Arr is 1
// time complexity to find 8 in the Arr is 5, because length of // Arr is 5
  • Best-Case complexity (Omega notation)
  • Worst-Case complexity (Big O notation)
  • Average-Case complexity (Theta notation)
  1. O(1) constant time complexity
Arr = [1, 2, 3, 4, 5, 6]
// initially, low is 0 and high is highest index which is length of Arr minus 1
low = 0
high = 6 - 1
mid = (low + high) / 2
mid = (0 + 5) / 2
  • Arr[mid] is equal to 5
  • If yes — return mid
  • If no —
  • Check Arr[mid] < 5. If yes, update low = mid + 1
  • Else check Arr[mid] > 5. If yes, update high = mid-1
For Array of length N = 8
O(logN) = O(log8)
we can say, 8 = 2 * 2 * 2
i.e 8 = 2^3
O(logN) = O(2^3)
O(logN) = 3 * O(2)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store