All Computer Science Resources
Example Questions
Example Question #31 : Program 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:
O(n log(n) )
O( )
O( n )
O( log(n) )
None of the above
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) ).
All Computer Science Resources
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
ACT Courses & Classes in Boston, ISEE Courses & Classes in Miami, LSAT Courses & Classes in Atlanta, Spanish Courses & Classes in Seattle, GRE Courses & Classes in Los Angeles, SAT Courses & Classes in Los Angeles, SSAT Courses & Classes in Seattle, MCAT Courses & Classes in Atlanta, GRE Courses & Classes in New York City, GMAT Courses & Classes in San Francisco-Bay Area
