String palindrome using dart with complexity calculation

Space and Time complexity of the program

In simple words space and time complexity of a program are almost similar as the number/unit of times a syntax of the program will run(takes that much number/unit of space)

Before calculating complexity, we take an assumption that we are calculating complexity for a very large input(worst case scenario)

Let’s calculate complexity of the above program. We will calculate complexity taking our least value as units(for both space or time).

• For main function[total ==3 units ]
• 1 unit for each string,list and print , i.e. total =3units for main function
• For checkpalindrome function
• Starting inside for loop
• 1 unit each for int i and j, i.e. 2 units
• Condition i>chars.length/2 will run n/2 times + 1 for exiting the loop, i.e. = n/2 + 1 units[assuming char.length = n].
• Similar for j statement n/2 +1 (it runs same as condition on i)
• Decrement operator i and increment operator j will run each n/2 times, i.e. =n units
• Total inside for loop = 2 + n/2 + 1 +n/2 + 1 + n ==2n + 3 units
• Conditional statement if will run once to check once but as it is inside for loop it will run 1 * n/2 times i.e. = n/2 units
• As we are taking the worst case so return statement will run which is inside the for loop i.e. ==1 unit
• Total inside the checkpalindrome function == 2n +3 + n/2 + 1 == 5n/2 + 4 units.
• Total in both function == 5n/2 + 4 + 3 = 5n/2 + 7 units.
• As we assumed earlier we are doing above calculations for very large inputs , so we will neglect the constants. Our program will have complexity of order of n
• Time and space complexity of the of the program is O(n)