Optimizing search in an E-Commerce Inventory

In e-commerce company manages a large inventory database with millions of products, each with attributes like price, stock level, and category. During peak sales events, the system frequently needs to search for a specific product ID in an unsorted list of items to check availability. Initially, they use a simple linear search, but performance issues arise as the database grows. The team wants to analyze alternatives like binary search (after sorting) to improve efficiency. Assignment Questions: Define the notion of an algorithm in this context and explain its characteristics (input, output, definiteness, finiteness, effectiveness). Design a pseudo code for linear search to find a product ID in the inventory array of size n. Analyze its time complexity in best, average, and worst cases using step count or operation count methods. If the inventory is sorted by product ID, design a recursive binary search algorithm. Set up a recurrence relation for its time complexity and solve it mathematically to find the asymptotic notation (Big O, Theta). Compare the time and space efficiency of linear search vs. binary search. Discuss why binary search might require preprocessing (sorting) and its impact on overall efficiency. Prove the correctness of the binary search algorithm using mathematical induction or loop invariants.

Analyzing Maximum Profit in Stock Market Data

A financial analytics firm processes daily stock price data for various companies to help investors identify the most profitable contiguous period (subarray) for buying and selling stocks. Given an array of daily price changes (positive or negative), they need to find the maximum subarray sum, which represents the highest cumulative gain over any consecutive days. Brute-force methods are too slow for large datasets, so they explore optimized algorithms. Assignment Questions: Explain the fundamentals of algorithmic problem solving for this maximum subarray sum problem, including understanding the problem, choosing exact vs. approximate solutions, and selecting data structures. Design a brute-force algorithm (O(n³)) using nested loops to compute all possible subarray sums. Analyze its time complexity mathematically for non-recursive algorithms. Improve it to an O(n²) version using prefix sums. Provide pseudo code and derive the time complexity, highlighting improvements in efficiency. Design an O(n) dynamic programming algorithm (non-recursive). Analyze its space complexity and use asymptotic notations to compare all three versions (Big O for upper bound). Discuss empirical vs. mathematical analysis: How would you visualize the efficiency (e.g., plot time vs. n) and apply this to real stock data with n=10^6?