1. what is the complexity of (a). accessing a binary tree, (b).accessing an arra

Question

1. what is the complexity of (a). accessing a binary tree, (b).accessing an array (c). accessing a hash map, (d). accessing a list, (e). accessing a file on disk.

2. you have a sorted array in which you need to find a value. the value may or may not be present in the array. Outline an algorithm to search for the value. what is the complexity of your alogorithm?

3. you have a weighted graph. Outline an algorithm to find a route from one node to another. what is the complexity of your algorithm?

4. which algorithm is faster? O(log(N)*log(N) or O(N)?

5. explain the difference between O(.), Omega(.), and Theta(.)

6. name two sorting algorithms with complexity faster than O(N*log(N)). in which situations can you not use these algorithms?

7. name two sorting algorithms with complexity faster than O(N^2)

Explanation / Answer

Ans1 -> Time complexities :

1. Accessing a binary tree : O(logn) for average case

                                         O(N) for worst case

2. Accessing an array : O(1) constant time

3. Accseeing an Hash map : O(1) constant.

4. Accessing a List : O(1)

5. Accessing a file on disk. O(N)

Ans->2 The algorithm we can use to find the value in the sorted array is binary search

Procedure binary_search
   A sorted array
   n size of array
   x value ot be searched
   Set lowerBound = 1
   Set upperBound = n
   while x not found
      if upperBound < lowerBound
         EXIT: x does not exists.
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      if A[midPoint] < x
         set lowerBound = midPoint + 1
      if A[midPoint] > x
         set upperBound = midPoint - 1
      if A[midPoint] = x
         EXIT: x found at location midPoint
   end while
end procedure

Ans-> 3 The Algorithm framed for the path from one node to another in a weighted graph is as (Dijkstra Algorithm):
        function Dijkstra(Graph, source):

       create vertex set Q

       for each vertex v in Graph:             // Initialization
           dist[v] INFINITY                  // Unknown distance from source to v
           prev[v] UNDEFINED                 // Previous node in optimal path from source
           add v to Q                          // All nodes initially in Q (unvisited nodes)

      dist[source] 0                        // Distance from source to source
    
      while Q is not empty:
          u vertex in Q with min dist[u]    // Source node will be selected first
          remove u from Q
        
          for each neighbor v of u:           // where v is still in Q.
              alt dist[u] + length(u, v)
              if alt < dist[v]:               // A shorter path to v has been found
                  dist[v] alt
                  prev[v] u

      return dist[], prev[]

      Time complexity of the above algorithm is O(V*V)
  
Ans 4-> In both of the time complexity O(log(N)*log(N) and O(N),
          using log properties, loga*logb= logab
       O(log(N)*log(N))= O(Nlog(N)),
         We can clearly see that O(N) is faster .       

Ans->6 Two sorting algorithms with complexity faster than O(N*log(N)) are :
    
       1. Counting sort which is non-comparison based sorting technique , has running time of O(n) and space of

           O(MaxMin+1) ,
            where n is # of elements in data structure and Max,Min elements belongs to data structure itself.
           Important point to note here is that we should be aware of range in data structure to efficient utilization of space.   
           Cannot be used when input is large.
       2. Radix sort which has time complexity of ((n+b)*d) where b is base of input numbers n # of element
          in integer array and d is the # digits is maximum number in array in worst case.
          For example if base is 10 then maximum possible value of d=logb(k), thus time complexity of radix sort is

          O((n+b)*logb(k)).
          radix sort is only useful for fix length integer keys

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.