All Computer Science Resources
Example Questions
Example Question #11 : Algorithm Analysis
for( int i = 0; i < n; ++i){
for( int j = 1; j < n; j *= 2){
someFunction();
}
}
For the code above, what is the run time in Big O notation?
Possible Answers:
None of the above
O(n log(n) )
O( )
O( n )
O( log(n) )
Correct answer:
O(n log(n) )
Explanation:
At first glance we might be tempted to pick O( ) because there are 2 for loops. But, upon closer inspection we can see that the first loop will yield a O( n ) running time but the second loop does not. The second loop has only an O( log(n) ) running time because "j" doubles each iteration and does not increase linearly. That will yield O( log(n) ) since O( log(n) ) is a much faster running time. So the final result is O( n log(n) ).
John
Certified Tutor
Certified Tutor
Dartmouth College, Bachelor in Arts, Mathematics and Computer Science. Purdue University-Main Campus, Master of Science, Comp...
All Computer Science Resources
Computer Science Tutoring in Top Cities:
Atlanta Computer Science Tutoring, Austin Computer Science Tutoring, Boston Computer Science Tutoring, Chicago Computer Science Tutoring, Dallas Fort Worth Computer Science Tutoring, Denver Computer Science Tutoring, Houston Computer Science Tutoring, Kansas City Computer Science Tutoring, Los Angeles Computer Science Tutoring, Miami Computer Science Tutoring, New York City Computer Science Tutoring, Philadelphia Computer Science Tutoring, Phoenix Computer Science Tutoring, San Diego Computer Science Tutoring, San Francisco-Bay Area Computer Science Tutoring, Seattle Computer Science Tutoring, St. Louis Computer Science Tutoring, Tucson Computer Science Tutoring, Washington DC Computer Science Tutoring
Computer Science Tutors in Top Cities:
Atlanta Computer Science Tutors, Austin Computer Science Tutors, Boston Computer Science Tutors, Chicago Computer Science Tutors, Dallas Fort Worth Computer Science Tutors, Denver Computer Science Tutors, Houston Computer Science Tutors, Kansas City Computer Science Tutors, Los Angeles Computer Science Tutors, Miami Computer Science Tutors, New York City Computer Science Tutors, Philadelphia Computer Science Tutors, Phoenix Computer Science Tutors, San Diego Computer Science Tutors, San Francisco-Bay Area Computer Science Tutors, Seattle Computer Science Tutors, St. Louis Computer Science Tutors, Tucson Computer Science Tutors, Washington DC Computer Science Tutors
Popular Courses & Classes
MCAT Courses & Classes in New York City, ACT Courses & Classes in Washington DC, SAT Courses & Classes in Chicago, SAT Courses & Classes in Denver, SAT Courses & Classes in Atlanta, ISEE Courses & Classes in San Diego, GRE Courses & Classes in Boston, SSAT Courses & Classes in Phoenix, MCAT Courses & Classes in Phoenix, GMAT Courses & Classes in Boston
Popular Test Prep
SSAT Test Prep in Washington DC, GMAT Test Prep in Atlanta, MCAT Test Prep in New York City, ISEE Test Prep in Atlanta, MCAT Test Prep in Atlanta, ISEE Test Prep in Miami, ISEE Test Prep in Philadelphia, GMAT Test Prep in Los Angeles, GRE Test Prep in San Francisco-Bay Area, ACT Test Prep in Houston
