🏷️ LIMITED TIME OFFER: GET 20% OFF GRADE+ YEARLY SUBSCRIPTION →
Log in
HomeClass Notes1,200,000US530,000

COM SCI 32 Lecture Notes - Lecture 8: Linear Search, Binary Search Algorithm, Time Complexity

155 views2 pages
cerisegiraffe538
30 Jul 2015
School
UCLA
Department
Computer Science
Course
COM SCI 32
Professor
Smallberg David

For unlimited access to Class Notes, a Class+ subscription is required.

Document Summary

For (i=0 ; i < n*n*n ; i++) sum += i; } O(log n): logarithmic complexity for ( int k = 0; k < q; k++ ) cout << muahahaha! ; else. Binary search in a sorted list of items cout << burp! ; } } While loop, decrementing condition (k>1) by half (k = k/2) O(n * log n) for (int i=0 ; i < n ; i++) { int k = n; while (k > 1) sum++; k = k/2; } O(n^2*q) void bar( int n, int q ) { for (int i=0 ; i < n*n ; i++) for (int j = 0; j < q; j++) cout << i love cs! ; If the pairs are in no particular order in the outer vector, the answer would be o(c + log s). The pairs are in no particular order in the outer vector.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents

COM SCI 32 Lecture Notes - Lecture 12: Merge Sort, Quicksort, Merge Algorithm
cerisegiraffe538
COM SCI 32 Lecture Notes - Lecture 11: Dynamic Array, Doubly Linked List, Virtual Function
cerisegiraffe538
COM SCI 32 Lecture Notes - Lecture 15: Binary Tree, Priority Queue, Multimap
viridiancattle279

Related Questions

Question 11. [5 MARKS] Each code fragment in the table below operates on list L, which has length k where k is very large - at least in the tens of thousands. For each fragment, give an expression in terms of k for how many times happy! is printed, and circle whether the behaviour is constant, linear, quadratic or something else. Code How many times is happy! printed? Complexity (circle one) for i in range (len (L)): print('happy!') for item in L: print('happy!') constant linear quadratic something else for i in range (len(L)) for item in L[:i]: print('happy!' constant linear quadratic something else # Precondition: len(L) % 10 == 0 i = 0 while i < len(L): print("happy!') i = i + len(L) // 10 constant linear quadratic something else for item in L[1000:2000] : print('happy!' constant linear quadratic something else for item in L[10:] : print('happy!' constant linear quadratic something else

16. The following method takes two integer arrays and a target integer as input. It is supposed to return true if there is an element from the first array and an element from the second array whose sum is the target integer. For instance, given arrays a=[1,4,3] and b=[2,6,3] and target 7, the method should return true because a[1]+b[2] = 4+3 = 7. However, if the target is 8, it should return false, as no element in array a, added with an element of array b results in 8. What should be the body of this method? public static boolean foo (int[] a, int[] b, int target) // What should go here? (A) for (int i = 0; i < a.length + b.length; i++) if(a[i] + b[i] == target) return true; else return false; (B) for (int i = 0; i