ANALYSIS BIG-O NOTATION

Important Topics for NET DAA

ANALYSIS BIG-O NOTATION

For each of the following pairs of functions f(n) and g(n), state whether f(n) =
O(g(n)), f(n) = ­Ω(g(n)), or f(n) = Θ(g(n)), or none of the above:


(a) f(n) = n2 + 3n + 4, g(n) = 6n + 7
Sol: f(n) = ­Ω(g(n).


(b) f(n) = n √n , g(n) = n2 - n
Sol: f(n) = O(g(n)).


(c) f(n) = 2**n - n**2, g(n) = n**4 + n**2
Sol: f(n) = ­­Ω(g(n).


(d) Assume you have five algorithms with the running times
listed below (these are the exact running times). How much slower do each of these
algorithms get when you double the input size
i) n²
Sol: 4T(n)

ii) n³
Sol: 8T(n)

iii) 100n²
Sol: 4T(n)

iv) nlgn
Sol: 2n(lg2n) = 2n(1+lgn) ~ 2n lgn
T(n) = 2T(n)

v) 2ⁿ
Sol:  [T(n)]² 


(e)  Write a big-O expression for 1+2+3+...+n?
Sol:  O(n²)


True or false:
(f) An algorithm with worst case time behavior of 3n takes at least 30 operations for every input of size n=10.
Sol : False


(g)  n! = O(nⁿ)
Sol: True


(h) n^O(1) = O(n²)
Sol: False.  O(1) can be any large constant .


(i) All of the following are true.

• f(n) = O(f(n))
• c * O(f(n)) = O(f(n)), if c is constant
• O(f(n)) + O(f(n)) = O(f(n))
• O(O(f(n))) = O(f(n))
• O(f(n)) * O(g(n)) = O(f(n)g(n))
• O(f(n)g(n)) = f(n) * O(g(n))
  

   

  MINIMUM SPANNING TREE

  1. In an undirected graph, the shortest path between two nodes lies on some minimum spanning
  tree.
  A: False.
  
  2. If the edges in a graph have different weights, then the minimum spanning tree is unique.
  A: True.
  
  3. If the edge with maximum weight belongs to a cycle, then there exists some MST that
  does not contain this edge.
  A: True
  
  4. Adding a constant to every edge weight does not change the minimum spanning tree.
  A: True
  
  5. There can be more than one minimum spanning trees if the weight of the edges are all distinct
  A.False
  
  6. If all weights are the same, every spanning tree is minimum.
  A. True
  
  7. Greedy algorithm runs in exponential time
  A. False
  
  8. A minimum spanning tree should contain all edges of the graph
  A. False
  
  9. A minimum spanning tree should contain all vertices of the graph
  A.True
  
  10.Adding an edge to a spanning tree of a graph G always creates a cycle.
  A.False
  
  11. Adding an edge to a spanning tree connecting two existing vertices of a graph G always creates a cycle.
  A. True
  
  12. For any cycle in a graph, the cheapest edge in the cycle is in a minimum spanning tree.
  A. False