Hi there I have been researching and trying to learn hw to check for the time complexity of certain algorithms. I've seen this video which was very helpful.
That being said I wondered off and started trying to work out the Worsts Case and average case of certain algorithms.
Program #1: This is a calculator which calculates in RPN format.
function evaluate() {
var input = prompt("Please enter your input string\n\nExamples of input strings:\n\n\t1. 10 4 5 + *\n\t2. 10 4 5 + * 2 +\n\t3. 10 8 *");
var values = input.split(" ");
var array = new Array();
for (i in values) {
if (values[i] != "+" && values[i] != "*" && values[i] != "-" && values[i] != "/") {
array.push(parseInt(values[i]));
} else {
var operator = values[i];
var val2 = array.pop();
var val1 = array.pop();
switch (operator) {
case "+":
array.push(eval("val1 + val2"));
break;
case "*":
array.push(eval("val1 * val2"));
break;
case "-":
array.push(eval("val1 - val2"));
break;
case "/":
array.push(eval("val1 / val2"));
break;
}
}
}
if (input == "" || input == null) {
document.writeln("Oops, based on your input we have nothing to calculate for you!");
} else {
document.writeln("Your RPN calculation is: ");
document.writeln(array + " with a starting input string of: " + input);
}
}
From what I've understood in this case the the for loop in this case is running for a constant number of times and that is the length of the array then performs a O(1) instruction hence the function reduce has a Time Complexity of O(1) no matter the size of the array passed.
Program #2: Check whether the number is Prime or Not
function isPrime(num) {
if(num <= 1) return false;
const limit = Math.floor(Math.sqrt(num));
for(let i = 2; i <= limit; i++) {
if(num % i === 0) return false;
}
return true;
}
Since there is one for loop and the program needs to at least look at every number from 2 to the inputted number hence I think it is O(n).
For now these are the one's I've done with lots of thinking and am hoping they are correct. My question is there an easy way on how to check the time complexity of functions I've never seen before.
P.S I THINK they are correct. Please if they aren't specify which and why.
Thanks for your help :)
Update
Apparently I was wrong and lexicore corrected me the answers are:
#1 No, it is not O(1). Assuming one step takes O(1) and you have n steps where n is the length of the array, time complexity is O(n).
#2 No, it is not O(n). You cycle makes at most sqrt(n) steps, each step O(1) so time complexity is O(sqrt(n)) here.
That being said I tried further and stumbled upon this in my textbook. It basically calculates an approximate square root.
#3
function sqrt(num) {
guess = num / 3;
do {
lastGuess = guess;
guess = (num / guess + guess) / 2;
while(Math.abs(lastGuess - guess));
return guess; /
Am I correct to say this is O(n) my reasoning is since we loop until an approx is found.
#4 from the user thanksd in the link he calculates the largest number in an array. Is it safe to say that the time complexity in this is O(n) since the largest number may be at the very last, and hence why O(n).
Thanks again
