Complexity Analysis for Interviews, Part 1

This is part 1 of a two part series. Skip over to part 2 you'd like .

For coding interviews, we are interested in gauging the asymptotic efficiency of algorithms both in terms of running time and space. The formal study of analysis of algorithms is called complexity theory, a rich field with fascinating and complicated math. For interviews, we only need a few basic concepts. Asymptotic efficiency is concerned with how the running time or memory requirements of an algorithm grows with the input size, so it is intimately concerned with how well algorithms scale to larger inputs. This is important in Computer Science and in practice because whereas some algorithms work well enough for small inputs of say < 10 inputs, the running time and space grows far faster than the input size and thus large inputs of say 10s to millions of inputs becomes impractical (usually meaning taking hours or even years of execution time). Consider sorting. Say for the sake of argument that sorting algorithm A takes 1, 2, 4, 16, 32, and so on seconds to sort 1, 2, 3, 4, 5, and so on elements and sorting algorithm B takes 1, 2, 3, 4, 5, and so on seconds for the same. The former algorithm would be considered exponential time or O(2^n) and the latter linear time O(n). Note that exponential time is really bad because for just 30 elements, you'd be talking about 12,427 hours of compute time. Instead of actually measuring the execution time of an already implemented algorithm, we can calculate a rough model for it via asymptotic notation.

First, to analyze the complexity of algorithms, there is a need to be precise: Are you interested in complexity in the worst case or average case? There is also best case performance, but you touch that less frequently. Some algorithms such as quicksort have good average cases (O(n log n) for quicksort) but poor worst case (O(n^2)). For interviews, usually the interviewer is interested in worst-case complexity, but if in doubt, ask. Before going further, let's get a good working definition of the most common form complexity analysis: Big O notation. Big O is the asymptotic upper bound of the growth of complexity.

Some common Big-O classes are, in the order of efficiency: O(1) constant < O(log n) logarithmic < O(n) linear < O(n log n) < O(n^2) quadratic < O(n^3) cubic < ... < O(2^n) exponential < ... < O(n!) factorial.

"Big-O" Class Name Representative algorithms
O(1)constant-timeinsertion into a linked list, lookup of a hash table with no collisions
O(log n)logarithmic-timebinary search on sorted array
O(n)linear-timelinear search, counting sort, iterate thru array a constant number of times, Boyer-Moore string search
O(n log n)quasilinear timemergesort, heapsort worst case, quicksort avg case, comparison-based sort, Dijkstra's shortest path (nonnegative edge weights)
O(n^3)cubic-timeFloyd-Warshall all-pairs shortest-path algorithm, Bellman-Ford
O(n^k)polynomial-timedynamic programming
O(2^n)exponential-timebacktracking algorithm
O(n!)factorial-timebrute-force search traveling salesman

Continue to part 2.

1. I ‘d mention that most of us visitors are endowed to exist in a fabulous place with very many wonderful individuals with very helpful things.

big data training in chennai

It looks like you spend a lot of effort and time on your blog.
I have bookmarked it and I am looking forward to reading new articles. Keep up the good work..
Best IELTS Coaching in Chennai
IELTS Coaching Center in Chennai
IELTS Coaching Center in Mumbai
Best IELTS Coaching Centers in Chennai
IELTS Classes in Chennai

3. I wondered upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I’ll be subscribing to your feed and I hope you post again soon.
best big data training in chennai
hadoop big data training in chennai

4. Thanks for your interesting ideas.the informations in this blog is very much useful
for me to improve my knowledge.
Best Java Training Institutes in Bangalore
Java Training institute in Anna Nagar
Java Courses in OMR

5. Awwsome informative blog ,Very good information thanks for sharing such wonderful blog with us ,after long time came across such knowlegeble blog. keep sharing such informative blog with us.
Aviation Academy in Chennai | Aviation Courses in Chennai | Best Aviation Academy in Chennai | Aviation Institute in Chennai | Aviation Training in Chennai

6. Great post! This is very useful for me and gain more information, Thanks for sharing with us.
English Speaking Course in Chennai
Spoken English Training center in Chennai
Spoken English Classes in Anna Nagar

7. good work done and keep update more.i like your information's and
that is very much useful for readers.
AWS Training Institutes in Bangalore
AWS Training in Thirumangalam
AWS Training in Amjikarai

8. It is very excellent blog and useful article thank you for sharing with us, keep posting.

Ethical Hacking
Hacking Course in Chennai
Ethical Hacking Training in Chennai
Certified Ethical HackingCours in Chennai

9. Thank you for sharing this post.

globalpayrollexpert
Guest posting sites

10. Great Articles, i am reading regularly very helpful for develop my knowledge. Thank you for this information. I would you like to more updates.
Blue Prism Training Centers in Bangalore
Blue Prism Institute in Bangalore
Blue Prism Training Institute in Bangalore
Blue Prism Training in Nolambur
Blue Prism Training in Mogappair

11. Such an excellent and interesting blog, do post like this more with more information, this was very useful, Thank you.
Air hostess training in Chennai
Air Hostess Training Institute in chennai
air hostess institute in chennai
best air hostess training institute in chennai

12. I have gone through your blog, it was very much useful for me and because of your blog, and also I gained much unknown information, the way you have clearly explained is really fantastic. Kindly post more like this, Thank You.
airport ground staff training courses in chennai
airport ground staff training in chennai
ground staff training in chennai

13. Only here are good game slots the casino best Come to us and get your winnings.

14. Enjoyed your approach to explaining how it works, hope to see more blog posts from you. thank you!

Article submission sites
Technology