Deciding a Big-O notation for an algorithm

by

Question 1 : O(n) because it increments by constant (1).
first loop O(n) second loop also O(n)
total O(n) + O(n) = O(n)

Question 2 : O(lg n) it’s binary search.

it’s O(lg n), because problem halves every time.

if the array is size n at first second is n/2 then n/4 ….. 1.

n/2^i = 1 => n = 2^i => i = log(n) .

More Related Contents:

  1. Stack with find-min/find-max more efficient than O(n)?
  2. Data Structure in Java
  3. How to check if an integer is in a set of given ranges? [closed]
  4. O(3^n) exponential time complexity [closed]
  5. How to merge two sorted arrays into a sorted array? [closed]
  6. How to detect a loop in a linked list?
  7. Anagram algorithm in java
  8. Sample Directed Graph and Topological Sort Code [closed]
  9. How to restore the PriorityQueue to its initial state before the method call?
  10. How to determine if binary tree is balanced?
  11. Hash : How does it work internally?
  12. How to implement a Median-heap
  13. The simplest algorithm for poker hand evaluation
  14. Finding the shortest path nodes with breadth first search
  15. Example of O(n!)?
  16. Given N number display M*M format [closed]
  17. Java: check if array is heap
  18. How to implement a tree data-structure in Java?
  19. How to print binary tree diagram in Java?
  20. Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
  21. Iteratively compute the Cartesian product of an arbitrary number of sets
  22. What are the time complexities of various data structures?
  23. print directory tree
  24. Most efficient way to see if an ArrayList contains an object in Java
  25. Randomly Generate Letters According to their Frequency of Use?
  26. What is the complexity of this simple piece of code?
  27. Find all numbers in the String [closed]
  28. Java algorithm to make a straight pyramid [closed]
  29. Fastest way of finding the middle value of a triple?
  30. Interview question – Search in sorted array X for index i such that X[i] = i

Leave a Comment