Hi Everyone!,
Today i would like to discuss further analysis of my code in terms of time and space complexity. This is the backend code.
[AllowAnonymous]
[HttpPost("registergoogle")]
public async Task<ActionResult<UserDto>> RegisterGoogle(GoogleRegisterDto googleRegisterDto)
{
GoogleJsonWebSignature.Payload payload;
try
{
payload = await GoogleJsonWebSignature.ValidateAsync(googleRegisterDto.GoogleTokenId);
}
catch (Exception ex)
{
return Unauthorized(new { Error = "Invalid google token" });
}
var email = payload.Email;
var displayName = payload.Name;
var userName = payload.Subject;
var existingUser = await _userManager.Users.FirstOrDefaultAsync(x => x.UserName == userName || x.Email == email || x.Us_DisplayName == displayName);
if (existingUser != null)
{
if (existingUser.Email == email)
{
return CreateUserObject(existingUser);
}else
{
ModelState.AddModelError("username", "Username taken");
return ValidationProblem();
}
}
var user = new AppUser
{
Us_DisplayName = displayName,
Email = email,
UserName = userName,
Us_Active = true,
Us_Customer = true,
Us_SubscriptionDays = 0
};
var result = await _userManager.CreateAsync(user);
if (result.Succeeded)
{
return CreateUserObject(user);
}
return BadRequest(result.Errors);
}
I will discuss each portion of the code with regards to its time and space complexity.
Here payload = await GoogleJsonWebSignature.ValidateAsync(googleRegisterDto.GoogleTokenId); in this line of code O(n) can be considered as O(1) considering network communication and cryptographic validation, or may be little higher or lower depending upon network communication. But, space complexity will be O(1) as assignment variable(payload).
Coming down, var email = payload.Email; These lines are also assignment variable hence both time and space complexity is O(1).
var displayName = payload.Name;
var userName = payload.Subject;
Now coming to line var existingUser = await _userManager.Users.FirstOrDefaultAsync(x => x.UserName == userName || x.Email == email || x.Us_DisplayName == displayName); Time complexity could be O(n) depending upon indexing and size of the AspnetUsers, where n is the no of users inside AspnetUsers table. So, we can simply measure the performance of this piece of code using stopwatch from System.Diagnostics. Hence my code look like this
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
var existingUser = await _userManager.Users.FirstOrDefaultAsync(x => x.UserName == userName || x.Email == email || x.Us_DisplayName == displayName);
stopwatch.Stop();
Console.WriteLine($"Exceution time after user query returned from db: {stopwatch.ElapsedMilliseconds}");
on first call it gives me the time as below.
It gives me a total time of 1165ms.
To improve the performance, since this query is related to db and is querying three parameters viz. Username, Email and Us_DisplayName on AspnetUsers. Hence, i have good option to create an index(non-clustered). I created an index on these parameters and measured the performance again. The result is below.
Time has reduced from 1165ms to 742ms.
Hence, we can say that time complexity has reduced from O(n) to O(log(n)) for indexed look up. while space complexity is O(1) as it stores reference to single user object only.
For the below piece of code time and space complexity would be O(1) as it involves condition check and method call only.
if (existingUser != null)
{
if (existingUser.Email == email)
{
return CreateUserObject(existingUser);
}else
{
ModelState.AddModelError("username", "Username taken");
return ValidationProblem();
}
}
Coming down to this lien ` Stopwatch stopwatch2 = new Stopwatch();
stopwatch2.Start();
var result = await _userManager.CreateAsync(user);
stopwatch2.Stop();
Console.WriteLine($"Exceution time after creating user: {stopwatch2.ElapsedMilliseconds}");`
I measured the performance again here which gives me around 314ms.
As this is database insert operation and practically it gives me 314ms, and hence time and space complexity could be considered again of O(1) considering proper indexing and db storage options.
Lastly, for this line
if (result.Succeeded)
{
return CreateUserObject(user);
}
return BadRequest(result.Errors);
Time and space complexity would be O(1) as this is condition checking and method call only.
Conclusion- step by step debugging through the code we were able to analyze the time and space complexity of the code and we have reduced space complexity from O(n) to O(log(n)) for look up operation using indexing.
This effort is a part of giving back to the community. I hope this would be helpful to some of us. Thanks for your time!
Ref used- https://stackoverflow.com/questions/4694574/database-indexes-and-their-big-o-notation, https://learn.microsoft.com/en-us/sql/relational-databases/indexes/indexes?view=sql-server-ver16
Top comments (0)