unit 1 - mathematical

If any program requires a fixed amount of time for all input values then its time complexity is said to be Constant Time Complexity

The absolute value function returns the distance of a number from zero on the number line, always resulting in a non-negative value.

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Θ notation is used to specify both the lower bound and upper bound of the function.

A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.

Indicates an algorithm that runs in constant time regardless of the input size.

Theta notation, represented by Θ, is used to describe the tight bound of an algorithm's running time. It indicates that the running time of the algorithm is bounded both from above and below by the given function.

The lower bound of an algorithm's time complexity.

Time requirements can be defined as a numerical function T(n), where T(n) can be measured as the number of steps, provided each step consumes constant time.

The asymptote of a curve is a line that closely approximates a curve but does not touch the curve at any point of time.

The remainder function, also known as the modulo operation, returns the remainder of the division of one number by another.

Theta notation (θ) is a mathematical notation used to describe both the upper and lower bounds of an algorithm's time complexity in terms of the input size.

Space complexity is a measure of the amount of memory space required by an algorithm to solve a computational problem as a function of the input size.

Average time required for program execution.

Space complexity is the total amount of memory space used by an algorithm/program including the space of input values for execution.

The space complexity S(P) of any algorithm P is given by S(P) = C + SP(I), where C is the fixed part and S(I) is the variable part of the algorithm which depends on instance characteristic I.

Big O notation is used to describe the upper bound of an algorithm's time complexity in the worst-case scenario.

A method used in asymptotic analysis to count the number of times a certain operation is executed in an algorithm.

Algorithms are a set of well-defined instructions for solving a problem or accomplishing a task. They can be represented using pseudocode, flowcharts, or programming languages.

The upper bound of an algorithm's time complexity.

The best case scenario of an algorithm refers to the minimum possible time or space required for the algorithm to complete its execution.

The worst case scenario of an algorithm refers to the maximum possible time or space required for the algorithm to complete its execution.

The property that states if f(n) is O(g(n)) and g(n) is O(h(n)), then f(n) is O(h(n)).

The remainder function, also known as the modulo operation, returns the remainder of the division of one number by another.

Asymptotic analysis is a method for describing the limiting behavior of a function when the argument tends towards a particular value or infinity.

The Summation Symbol is used to represent the sum of a series of numbers or terms.

The Summation Symbol is denoted by the Greek letter sigma (∑).

A mathematical notation that describes the upper bound of an algorithm's time complexity in terms of how it scales with the size of the input.

A function representing the time complexity of an algorithm, where n is the size of the input.

The time complexity of an algorithm is a measure of the amount of time it takes to run as a function of the length of the input. It gives an upper bound on the running time in terms of the input size.

O(n2)

Frequency is defined as the total number of times each statement is executed.

Asymptotic analysis of an algorithm refers to defining the mathematical boundation/framing of its run-time performance.

T1(n) * T2(n)

c is the time taken for addition of two bits.

The floor function returns the largest integer less than or equal to a given number, while the ceiling function returns the smallest integer greater than or equal to a given number.

The summation symbol, often denoted by the Greek letter sigma, represents the addition of a sequence of numbers or terms.

Little-oh notation (o) is a mathematical notation used to describe the upper bound of an algorithm's time complexity in terms of the input size, excluding the exact bound.

Time complexity is a measure of the amount of time required by an algorithm to solve a computational problem as a function of the input size.

Minimum time required for program execution.

Represents the tight bound of a function, denoting both the upper and lower bounds.

O(n)

Big-Omega notation (Ω) is used to describe the best-case scenario of an algorithm's time complexity. It represents the lower bound of the running time of an algorithm.

A function t(n) is said to be in Ω(g(n)), denoted as t(n) ϵ Ω(g(n)), if t(n) is bounded below by some positive constant multiple of g(n) for all large n. i.e., there exist some positive constant c and some non-negative integer n0. Such that t(n) ≥ cg(n) for all n ≥ n0. It represents the lower bound of the resources required to solve a problem.

proportional to n

The sum of c1, c2, (n+1)c3, nc4, n*(n+1)c5, nnc6, nnc7, and nc8

Proportional to n^2

The notation Θ(n2 ) signifies that the running time of an algorithm grows at the same rate as n2, within a constant factor. It provides a tight bound on the algorithm's time complexity.

The set of functions that grow at least as fast as g(n) for sufficiently large n.

The property that states a function f(n) is always O(f(n)).

Big-Oh notation (O) is a mathematical notation used to describe the upper bound of an algorithm's time complexity in terms of the input size.

Big O notation is used to describe the upper bound of an algorithm's time complexity in terms of how it grows relative to the size of the input.

Space complexity is a measure of the amount of memory space required by an algorithm to solve a computational problem as a function of the input size.

A mathematical notation used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity.

The measure of the amount of resources required to perform a particular algorithm or operation, such as time, space, or both.

The concept of sacrificing space to reduce the time complexity of an algorithm, or sacrificing time to reduce the space complexity.

c1 + c2 + (n+1)c3 + nc4 + n*c5

The amount of memory space required by an algorithm or program to execute as a function of the input size. In this case, it is calculated as size(a) + size(b) + size(c), where sizeof(int) = 2 bytes, resulting in 6 bytes. Therefore, the space complexity is O(1) or constant.

The function that gives the positive value of the given input.

K (mod) M gives the reminder of K divided by M.

Mathematical function, algorithm's time complexity.

Time Complexity of an algorithm represents the amount of time required by the algorithm to run to completion.

The set of functions that grow at the same rate as g(n) for sufficiently large n.

The floor function returns the largest integer less than or equal to a given number, while the ceiling function returns the smallest integer greater than or equal to a given number.

Big-Omega notation (Ω) is a mathematical notation used to describe the lower bound of an algorithm's time complexity in terms of the input size.

Big Omega notation is used to describe the lower bound of an algorithm's time complexity in terms of how it grows relative to the size of the input.

Time complexity is a measure of the amount of time required by an algorithm to solve a computational problem as a function of the input size.

Logarithms are the inverse operation to exponentiation. They indicate the power to which a base must be raised to produce a given number.

The best case occurs if the array is already sorted, tj=1 for j=2,3…n.

Big-Omega notation (Ω) is used to describe the lower bound of an algorithm's time complexity. It represents the minimum time required for an algorithm to run in relation to the input size.

t(n) is a function that represents the time complexity of an algorithm. In this context, t(n) = 2n + 3.

A data structure that stores a collection of elements, each identified by at least one array index or key.

The s/e of a statement is the amount by which the count changes as a result of the execution of that statement.

A function used in Big-O notation to represent the scaling behavior of an algorithm's time complexity with respect to the size of the input.

Combining s/e and frequency, the step count for the entire algorithm is obtained.

Space complexity is a measure of the amount of memory space required by an algorithm to execute in terms of the input size. It is calculated by considering the total space required to store the data used in the program, including the size of variables and any additional space needed.

O(1) denotes constant space complexity, indicating that the amount of memory space required by the algorithm does not increase with the size of the input.

The property that states if f(n) is θ(g(n)), then g(n) is also θ(f(n)).

The summation symbol represents the addition of a sequence of numbers, often denoted as the Greek letter sigma (∑).

Big O notation is used to describe the upper bound of an algorithm's time complexity in terms of how it grows with respect to the size of the input.

Space complexity is a measure of the amount of memory space required by an algorithm to solve a computational problem as a function of the input size.

Theta is a notation used in the analysis of algorithms to describe the tight bound of the running time. It represents the average case time complexity of an algorithm.

Permutations refer to the arrangement of objects in a specific order. In mathematics, it is denoted by nPr, where n represents the total number of items and r represents the number of items taken at a time.

The space complexity of the program is O(n) or linear, as the space occupied by the array and integer variables is 4n + 12 bytes.

A method used to find the time complexity for an algorithm by counting the number of basic operations executed in the algorithm.

A constant value used in Big-O notation to represent the scaling factor of the upper bound of an algorithm's time complexity.

A data type used to represent whole numbers, which can be positive, negative, or zero.

The table method is a technique used to analyze and calculate the time complexity of algorithms by creating a table to track the number of operations performed at each step of the algorithm.

Big O Notation is used to specify the upper bound of the function.

The integer data type is a data type that represents whole numbers. In this example, the size of the integer data type is assumed to be 4 bytes, which depends on the architecture of the system (compiler).

T(n) grows linearly as input size increases.

The remainder function, also known as the modulo operation, returns the remainder of the division of one number by another.

Asymptotic analysis is a method for describing the limiting behavior of a function when the argument tends towards a particular value or infinity.

Big Omega notation is used to describe the lower bound of an algorithm's time complexity in terms of how it grows relative to the size of the input.

An integer is a whole number that can be positive, negative, or zero, and does not have a fractional or decimal part.

Asymptotic notation is a mathematical notation used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity.

Theta notation is used to describe the behavior of a function in terms of both upper and lower bounds, providing a precise description of the growth rate of the function.

If the array is in reverse sorted order

In the algorithm SUM(A, B), the space complexity S(P) is calculated as 1+3, where 1 represents the constant and 3 represents the variables A, B, and C.

Big Omega notation is used to describe the lower bound of an algorithm's time complexity in the best-case scenario.

The amount of memory space required by an algorithm or program to solve a computational problem as a function of the size of the input.

The function n2 /2 – 2n represents the running time of an algorithm. It is used to analyze the time complexity of the algorithm and compare it with other functions to determine its growth rate.

The set of functions that grow no faster than g(n) for sufficiently large n.

The theory of approximation is related to the behavior of an algorithm when the input size increases, and it involves deriving the best, average, and worst case scenarios of the algorithm.

The property that states if f(n) = O(g(n)), then g(n) is Ω(f(n)).

Asymptotic analysis is a method for describing the limiting behavior of a function when the argument tends towards a particular value or infinity.

Big Omega notation is used to describe the lower bound of an algorithm's time complexity in terms of how it grows with respect to the size of the input.

The time complexity of the insertion sort algorithm is O(n^2) in the worst case, where n is the number of elements being sorted.

A function t(n) is said to be in O(g(n)), denoted as t(n) ϵ O(g(n)), if t(n) is bounded above by some constant multiple of g(n) for all large n. i.e., if there exist some positive constant c and some non-negative integer n0 such that t(n) ≤ cg(n) for all n ≥ n0

The remainder function, also known as modular arithmetic, calculates the remainder of the division of one number by another.

The floor function returns the largest integer less than or equal to a given number, while the ceiling function returns the smallest integer greater than or equal to a given number.

Maximum time required for program execution.

Big-Oh notation is used to describe the upper bound of an algorithm's time complexity in terms of the input size.

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. Its time complexity is O(n^2) in the worst case, where n is the number of elements in the array.

A method used to find the time complexity for an algorithm by creating a table to track the number of operations executed at each step of the algorithm.

A simple sorting algorithm that builds the final sorted array one item at a time.

For a given set of number n, the number of possible permutation will be equal to the factorial value of n.

The average case scenario of an algorithm refers to the expected time or space required for the algorithm to complete its execution when given an average input.

Asymptotic analysis is input bound, meaning it specifies the behavior of the algorithm when the input size increases.

The floor function returns the largest integer less than or equal to a given number, while the ceiling function returns the smallest integer greater than or equal to a given number.

The summation symbol, denoted by the Greek letter sigma, represents the sum of a series of terms in mathematics.

Big O notation is used to describe the upper bound of an algorithm's time complexity in terms of how it grows relative to the size of the input.

Time complexity is a measure of the amount of time required by an algorithm to solve a computational problem as a function of the input size.

Little-omega notation (ω) is a mathematical notation used to describe the lower bound of an algorithm's time complexity in terms of the input size, excluding the exact bound.

The time complexity of the insertion sort algorithm is O(n^2) in the worst case, where n is the number of elements being sorted.

The time complexity of the insertion sort algorithm is O(n^2) in the worst case, where n is the number of elements being sorted.

Exponents are a mathematical notation that indicates the number of times a number is multiplied by itself.

The factorial function is a mathematical function denoted by the symbol '!', which takes a non-negative integer as input and returns the product of all positive integers less than or equal to the input.