### 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 )

O( log(n) )

O(n log(n) )

O( )

**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) ).

Benjamin

Certified Tutor

Certified Tutor

Johns Hopkins University, Bachelor in Arts, Mathematics. Johns Hopkins University, Bachelor of Science, Electrical Engineering.

### 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 San Diego, Spanish Courses & Classes in Los Angeles, LSAT Courses & Classes in San Francisco-Bay Area, SSAT Courses & Classes in Phoenix, Spanish Courses & Classes in San Diego, GRE Courses & Classes in Philadelphia, GMAT Courses & Classes in Houston, ISEE Courses & Classes in Houston, SAT Courses & Classes in Seattle, Spanish Courses & Classes in Boston
Popular Test Prep

MCAT Test Prep in Chicago, SAT Test Prep in Boston, ISEE Test Prep in San Francisco-Bay Area, LSAT Test Prep in Chicago, ACT Test Prep in San Diego, SAT Test Prep in Atlanta, GMAT Test Prep in Houston, LSAT Test Prep in Houston, GRE Test Prep in Atlanta, SSAT Test Prep in San Francisco-Bay Area