time complexity

Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element). Problem: Given an array consisting of N integers, find the number with the maximum occurrences, i.e. majority element, given the assumption that the number occurs more than N/2 times in the array. Example I/P : 3 3 4 2 4 4 2 4 4 [Read More]

Definition A balanced search tree is a tree which can provide operations like insert, delete and search in O(lg n) where n is the height of tree and lg n is height. Motivation behind Balanced Search tree Properties of sorted array Consider the sorted array. If we have a sorted array, what kinds of operations can we perform on it? Binary search in O(logn) time. (We use binary search) Select element given ith order statistic in O(1) Computing min/max of array - O(1) Predecessor/Successor - O(1), just find that element and return one before/after it Rank - how many keys stored are less than or equal to the key - O(logn) Output in sorted order - O(n) Simply using a sorted array would be unacceptable for insertion/deletion because it could use O(n) time. [Read More]

Hoore cisca discovered it in 1961. Why quicksort? Definitely a greatest hit algorithm  Prevalent in practice O(n log n) time “on average” minimal extra memory needed (which gives it leverage over merge sort) The sorting problem Input: Array of numbers , unsorted. Eg. Output : Same numbers sorted in some order, say increasing order. Eg. Quicksort helps us solving this problem. What is quick sort? [Read More]

Recurrence Relations Recurrence relations often arise in calculating the time and space complexity of algorithms. The amount of time (or space) that a program takes, Tk, is typically a function of the size, k, of the input data. A recurrence relation arises when Tk is some function of Tk’ for k’ Logarithmic Complexity The following recurrence **Tk = Tk/2 + a if k!=1 = b if k=1 ** has the solution [Read More]