Hacks
hundnumbers = list(range(100))
tennumbers = list(range(10))
Testing the Timing Of Each with hundnumbers
import time
hundnumbers = list(range(100))
# linear
start_time = time.time()
for num in hundnumbers:
if num == 90:
print("Found 90")
end_time = time.time()
total_time = end_time - start_time
print("Time taken for linear search:", total_time, "seconds")
# quadratic
start_time = time.time()
for num in hundnumbers:
for num2 in hundnumbers:
if num == 90 and num2 == 90:
print("Found 90")
end_time = time.time()
total_time = end_time - start_time
print("Time taken for quadratic search:", total_time, "seconds")
# logarithmic
def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1
start_time = time.time()
index = binary_search(hundnumbers, 0, len(hundnumbers)-1, 90)
if index != -1:
print("Found 90 at index", index)
end_time = time.time()
total_time = end_time - start_time
print("Time taken for binary search:", total_time, "seconds")
# exponential
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
start_time = time.time()
result = fibonacci(15)
print("Fibonacci(15) =", result)
end_time = time.time()
total_time = end_time - start_time
print("Time taken for fibonacci(15):", total_time, "seconds")
import time
hundnumbers = list(range(100))
tennumbers = list(range(10))
# linear
start_time = time.time()
for num in hundnumbers:
if num == 8:
pass
end_time = time.time()
total_time = end_time - start_time
print("Time taken for linear search:", total_time, "seconds")
# quadratic
start_time = time.time()
for num in hundnumbers:
for num2 in hundnumbers:
if num == 8 and num2 == 8:
pass
end_time = time.time()
total_time = end_time - start_time
print("Time taken for quadratic search:", total_time, "seconds")
# logarithmic
def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1
start_time = time.time()
index = binary_search(tennumbers, 0, len(tennumbers)-1, 8)
if index != -1:
print("Found 8 at index", index)
end_time = time.time()
total_time = end_time - start_time
print("Time taken for binary search:", total_time, "seconds")
# exponential
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
start_time = time.time()
result = fibonacci(8)
print("Fibonacci(8) =", result)
end_time = time.time()
total_time = end_time - start_time
print("Time taken for fibonacci(8):", total_time, "seconds")
Hacks Questions
- Record your findings when testing the time elapsed of the different algorithms.
- Although we will go more in depth later, time complexity is a key concept that relates to the different sorting algorithms. Do some basic research on the different types of sorting algorithms and their time complexity. Selection sort/Bubble sort/Insertion sort: O(n^2)
Heap/Quick/Merge: O(n log(n)) Bucket/Count sort: O(n+k) Radix sort: O(nk)
- Why is time and space complexity important when choosing an algorithm?
Time and space complexity are important when choosing an algorithm because you want to choose the algorithm that requires the least space and time to run, so investigating this will help your program achieve maximum efficiency.
- Should you always use a constant time algorithm / Should you never use an exponential time algorithm? Explain?
You should sometimes use an exponential time algorithm because at lower values and less data values, they can be faster than constant time algorithms. It just depends on how much data you'r eprocessing.
- What are some general patterns that you noticed to determine each algorithm's time and space complexity?
Some general patterns I noticed were that loops often determine the time complexity. Look for the general structure of the program as well as nested for loops.
Complete the Time and Space Complexity analysis questions linked below. Practice
Time and Space Complexity Practice
a = 0 b = 0 for i in range(N): a = a + random()
for i in range(M): b= b + random()
Answer: O(N + M) time, O(1) space because the first and second loo pare independent, so you have to add N and M, you can't multiply them.
a = 0; for i in range(N): for j in reversed(range(i,N)): a = a + i + j
Answer: O(N^2) This is a nested for loop, so it runs N*N times.
k = 0; for i in range(n//2,n): for j in range(2,n,pow(2,j)): k = k + n / 2;
Answer: O(nLogn) J keeps doubling until it is less than or equal to n, so log would be used.
a = 0 i = N while (i > 0): a += i i //= 2
Answer: O(log N) Log is used here because it will sto pafter a certain time.
Which of the following best describes the useful criterion for comparing the efficiency of algorithms?
Time Memory Both of the above None of the above
Answer: Both of the above because you should consider both space and time, to consider the speed and memory the program will take, in order to achieve maximum efficiency.
How is time complexity measured?
By counting the number of algorithms in an algorithm. By counting the number of primitive operations performed by the algorithm on a given input size. By counting the size of data input to the algorithm. None of the above
Answer: By counting the number of primitive operations performed by the algorithm on a given input size
Code
for i in range(n): i=i*k
Answer: O(logk(n)) because the loop goes through k^n-1 times
value = 0; for i in range(n): for j in range(i): value=value+1
Answer: n(n-1) because the first loop will run n times and the other loop will run (n-1) times.
Algorithm A and B have a worst-case running time of O(n) and O(logn), respectively. Therefore, algorithm B always runs faster than algorithm A.
True False
Answer: False because it depends on what n is.