Running Time Analysis

Interviewers are very interested in whether or not you understand the efficiency of your algorithm, in both running time and space constraints.

Efficiency is usually measured using Big-O analysis, which estimates the worst case scenario of the time it takes for an algorithm to run given an input size of n.

Big-O represents worst case analysis, Big-Theta represents average case, and Big-Omega represents best case. As programmers, we are almost always interested in the worst case scenario, so we'll focus on Big-O analysis.

Big-O analysis is very useful because it allows a programmer to predict an algorithm's running time without having to implement it and run benchmarks.

Since Big-O analysis only cares about the asymptotic running time of the algorithm, it is a rough guess, but the advantage is in not having to worry about the minute details.

Common Running Times and Scenarios

O(1) Insertion and deletion for arrays due to random access.
Insertion and deletion of the head element in linked lists.
Insertion and deletion of the root element in heaps.
O(log n) Binary search in arrays.
Insertion, deletion, and balancing of binary search trees.
O(n) Linked list traversal.
O(nlogn) Sorting.
O(n^2)
O(2^n) Very bad.
NP complete problems are of this class.
Traveling salesman
O(n!) Even worse...

Steps for performing Big-O analysis:

  • Determine what n represents. Nodes in a linked list? Size of an array? Number of vertices in a graph?
  • Define an operation. Addition? Comparison? Search?
  • Find out how many operations are performed on the input size n.
  • Ignore lower order terms and constant factors.

NOTE: Some algorithms require Big-O notation using two or more variables: for example, graph algorithm running times are often expressed as O(ve), v for the number of vertices and e for the number of edges.

You should be familiar with the Big-O running time for all of the popular algorithms out there and understand why it takes that long. Keep in mind that the underlying data structure used by an algorithm may change the running time.

Practice Question: Fill in the Big-O running times for these operations.

Insert into array O(1)
Delete entry from array O(1)
Search in sorted array O(log n)
Insert to head of linked list O(1)
Insert to tail of linked list O(n)
Search in linked list O(n)
Insert into binary search tree O(log n)
Balance binary search tree O(log n)
Search for element in binary search tree O(log n)

Webfaction is the ULTIMATE hosting platform for any serious developer.
SSH, WordPress, Rails, Django, cronjobs, compile and execute anything.
ProgrammingInterview.com is proudly powered by Webfaction.